Editorial for Vận chuyển hàng
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define iii pair<int, ii> #define X first #define Y second const int N = 111; const double eps = 1e-4; using namespace std; vector<iii> e; int n, m; double d[N]; bool Relax(iii e, double w) { bool ret = d[e.Y.X] + e.X - w < d[e.Y.Y]; if (ret) d[e.Y.Y] = d[e.Y.X] + e.X - w; return ret; } bool NC_exist(double avg) { //check if there is a negative cycle using BellmanFord Alg //each edge is decreased by avg int i, j; bool stop; for(i = 1; i <= n; i++) d[i] = 0; for(i = 1; i < n; i++) { stop = true; for(j = 0; j < m; j++) if (Relax(e[j], avg)) stop = false; if (stop) break; } for(j = 0; j < m; j++) if (Relax(e[j], avg)) return true; return false; } int main() { //freopen("QBTRANS.in", "r", stdin); scanf("%d %d\n", &n, &m); int i, u, v, c; for(i=0; i<m; i++) { scanf("%d %d %d\n", &u, &v, &c); e.push_back(iii(c, ii(u, v))); } double l = 0, r = 1e9, mid, res = -1; while (r - l > eps) { mid = (l + r) / 2; if (NC_exist(mid)) { res = mid; r = mid; } else l = mid; } if (res < 0 || res > 1e8) printf("-1"); else printf("%.2f", res); return 0; }
Code mẫu của RR
//Written by Nguyen Thanh Trung {$R-,Q-} {$Mode objFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 111; gh = 10; eps = 5e-3; oo = 1000111000; type real = extended; Tedge = record u,v,c:longint; end; var f1,f2 : text; n,m : longint; edge : array[1..MAXN*MAXN] of Tedge; d : array[1..MAXN] of real; trace : array[1..MAXN] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n,m); for i:=1 to m do with edge[i] do read(f1,u,v,c); end; function check(val:real):boolean; inline; var found:boolean; i,nn:longint; begin fillchar(d,sizeof(d),0); for nn:=1 to gh do begin fillchar(trace,sizeof(trace),0); found:=false; for i:=1 to m do with edge[i] do if d[v]>d[u]+c-val+eps then begin trace[v]:=u; d[v]:=d[u]+c-val; found:=true; end; if not found then exit(true); end; exit(false); end; function findMax:longint; var i,kq:longint; begin kq:=0; for i:=1 to m do kq:=max(kq,edge[i].c); exit(kq); end; procedure solve; var l,r,mid,kq:real; begin kq:=-1; l:=0; r:=findMax+eps; while l<r do begin mid:=(l+r)/2; if not check(mid) then begin kq:=mid; r:=mid-eps; end else l:=mid+eps; end; if check(kq) then begin end; if kq=-1 then writeln(f2,kq:0:0) else writeln(f2,trunc(kq*100)/100:0:2); end; begin openF; inp; solve; closeF; end.
Code mẫu của khuc_tuan
#include <iostream> #include <queue> using namespace std; int n, m; int a[111][111]; double d[111]; bool inq[111]; int step[111]; int main() { scanf("%d%d", &n, &m); for(int i=0;i<m;++i) { int u, v, c; scanf("%d%d%d", &u, &v, &c); if(a[u][v]==0) a[u][v] = c; else a[u][v] <?= c; } double left = 0, right = 1e7; for(int kk=0;kk<40;++kk) { double mid = (left+right) / 2; queue<int> q; for(int i=1;i<=n;++i) d[i] = 0, q.push(i); memset( inq, true, sizeof(inq)); memset( step, 0, sizeof(step)); bool OK = false; while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for(int v=1;v<=n;++v) if(a[u][v] > 0 && d[v] > d[u] + a[u][v] - mid) { d[v] = d[u] + a[u][v] - mid; step[v] = step[u] + 1; if(step[v] >= n + 3) { OK = true; goto lab; } if(!inq[v]) { inq[v] = true; q.push(v); } } } lab : ; if(OK) right = mid; else left = mid; } // cout << left << " " << right << endl; if(left > 1e7 - 2) cout << -1 << endl; else printf("%.2f\n", left); // system("pause"); return 0; }
Comments