Editorial for Bảo vệ
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 flashmt
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; const int oo = 1 << 29; struct edge { int x, y, cap, flow; }; struct Flow { int n, S, T; vector < vector <int> > a; vector <int> cur, d; vector <edge> e; Flow() {} Flow(int _n, int _S, int _T) { n = _n; S = _S; T = _T; a = vector < vector <int> >(n + 1); cur = vector <int>(n + 1); d = vector <int>(n + 1); } void addEdge(int x, int y, int _cap) { edge e1 = {x, y, _cap, 0}; edge e2 = {y, x, 0, 0}; a[x].push_back(e.size()); e.push_back(e1); a[y].push_back(e.size()); e.push_back(e2); } int bfs() { queue <int> q; for (int i = 1; i <= n; i++) d[i] = -1; q.push(S); d[S] = 0; while (!q.empty() && d[T] < 0) { int x = q.front(); q.pop(); for (int i = 0; i < int(a[x].size()); i++) { int id = a[x][i], y = e[id].y; if (d[y] < 0 && e[id].flow < e[id].cap) q.push(y), d[y] = d[x] + 1; } } return d[T] >= 0; } int dfs(int x, int val) { if (!val) return 0; if (x == T) return val; for (; cur[x] < int(a[x].size()); cur[x]++) { int id = a[x][cur[x]], y = e[id].y; if (d[y] != d[x] + 1) continue; int pushed = dfs(y, min(val, e[id].cap - e[id].flow)); if (pushed) { e[id].flow += pushed; e[id ^ 1].flow -= pushed; return pushed; } } return 0; } int maxFlow() { int res = 0; while (bfs()) { for (int i = 1; i <= n; i++) cur[i] = 0; while (1) { int val = dfs(S, oo); if (!val) break; res += val; } } return res; } int minCut() { maxFlow(); int res = 0; for (int x = 1; x <= n; x++) if (d[x] >= 0) for (int i = 0; i < int(a[x].size()); i++) { int id = a[x][i], y = e[id].y; if (d[y] < 0) res += e[id].cap; } return res; } }; int main() { int n, x, y, z; cin >> n; Flow u(n, n, 1); while (scanf("%d%d%d", &x, &y, &z) == 3) u.addEdge(x, y, z); cout << u.minCut() << endl; }
Code mẫu của happyboy99x
#include<cstdio> #include<vector> #include<queue> #include<cstring> using namespace std; #define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i) const int N = 5005; struct edge { int u, c, f; edge(){} edge(int u, int c): u(u), c(c), f(0) {} }; vector<vector<edge> > g; int n, s, t, trace[N]; void addEdge(int u, int v, int d) { TR(g[u], i) if(i->u == v) { i->c += d; return; } g[u].push_back(edge(v, d)); } void addFlow(int u, int v, int d) { TR(g[u], i) if(i->u == v) { i->f += d; return; } } void enter() { scanf("%d", &n); g.resize(n); s = n-1; t = 0; for(int u, v, d; scanf("%d%d%d",&u,&v,&d) == 3; ) { --u; --v; addEdge(u, v, d); addEdge(v, u, 0); } } int FindPath() { memset(trace, 0, sizeof trace); trace[s] = -1; queue<pair<int, int> > q; q.push(pair<int, int>(s, 1000000000)); while(!q.empty()) { int u = q.front().first, f = q.front().second; q.pop(); TR(g[u], i) if(trace[i->u] == 0 && i->c > i->f) { trace[i->u] = u; q.push(pair<int, int>(i->u, min(f, i->c - i->f))); if(i->u == t) return min(f, i->c - i->f); } } return -1; } void MaxFlow() { int res = 0; for(int inc; (inc = FindPath()) != -1; ) { res += inc; int v = t; do { int u = trace[v]; addFlow(u, v, inc); addFlow(v, u, -inc); v = u; } while(v != s); } printf("%d\n", res); } int main() { enter(); MaxFlow(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 5001; const int oo = 1000000009; using namespace std; int f[N][N], c[N][N], n, Q[N], T[N]; vector<int> a[N]; bool BFS() { int l = 1, r = 1, i, u, v; Q[1] = n; for(i=1; i<=n; i++) T[i] = 0; while (l<=r) { u = Q[l++]; for(i=0; i<a[u].size(); i++) { v = a[u][i]; if (T[v] == 0 && c[u][v]>f[u][v]) { Q[++r] = v; T[v] = u; if (v == 1) return true; } } } return false; } void IncFlow() { int v = 1, delta = oo, u; while (v != n) { u = T[v]; delta = min(delta, c[u][v] - f[u][v]); v = u; } v = 1; while (v != n) { u = T[v]; f[u][v] += delta; f[v][u] -= delta; v = u; } } int main() { //freopen("BAOVE.in", "r", stdin); scanf("%d\n", &n); int u, v, w; while (scanf("%d %d %d\n", &u, &v, &w) == 3) { a[u].push_back(v); a[v].push_back(u); c[u][v] += w; } while (BFS()) IncFlow(); int s = 0; for(int i = 0; i<a[n].size(); i++) s += f[n][a[n][i]]; printf("%d", s); return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung {$R+,Q+} PROGRAM BAOVE; CONST fi=''; fo=''; maxn=5000; max=10000; oo=1000000000; TYPE rec=record v:integer; c:longint; end; rec2=record u,v:integer; c:longint; end; VAR n:integer; queue,cv,trace,degt,degn,th1,th2:array[1..maxn] of integer; first,last:integer; xet:array[1..maxn] of byte; dt:array[1..maxn] of longint; et,en:array[1..max] of rec; ft:array[1..max] of longint; s1,s2:array[1..maxn+1] of integer; dscanh:array[1..max] of rec2; m:integer; f1,f2:text; fl:longint; Procedure OpenFiles; Begin Assign(f1,fi); Reset(f1); Assign(f2,fo); Rewrite(f2); End; Procedure CloseFiles; Begin Close(f1); Close(f2); End; Procedure ReadInput; Begin Readln(f1,n); m:=0; While not Eof(f1) do begin inc(m); with dscanh[m] do Readln(f1,u,v,c); end; End; Procedure Trans; Var i:integer; Begin For i:=1 to m do with dscanh[i] do begin inc(degt[u]); inc(degn[v]); end; s1[1]:=1; For i:=1 to n do s1[i+1]:=s1[i]+degt[i]; s2[1]:=1; For i:=1 to n do s2[i+1]:=s2[i]+degn[i]; For i:=1 to m do with dscanh[i] do begin et[s1[u]+th1[u]].v:=v; et[s1[u]+th1[u]].c:=c; inc(th1[u]); en[s2[v]+th2[v]].v:=u; en[s2[v]+th2[v]].c:=s1[u]+th1[u]-1; inc(th2[v]); end; End; Procedure Init; Begin Fillchar(dt,sizeof(dt),0); dt[n]:=oo; Fillchar(xet,sizeof(xet),0); xet[n]:=1; first:=1; last:=1; queue[first]:=n; trace[n]:=0; End; Function min(a,b:longint):longint; Begin if a<=b then min:=a else min:=b; End; Procedure FindPath; Var u,v,i:integer; Begin while first<=last do begin u:=queue[first]; inc(first); for i:=s1[u] to s1[u+1]-1 do with et[i] do if (xet[v]=0) and (c-ft[i]>0) then begin xet[v]:=1; inc(last); queue[last]:=v; trace[v]:=u; cv[v]:=i; dt[v]:=min(dt[u],c-ft[i]); end; for i:=s2[u] to s2[u+1]-1 do with en[i] do if (xet[v]=0) and (ft[c]>0) then begin xet[v]:=1; inc(last); queue[last]:=v; trace[v]:=-u; cv[v]:=c; dt[v]:=min(dt[u],ft[c]); end; if dt[1]>0 then exit; end; End; Procedure IncFlow; Var x,pre:integer; Begin x:=1; repeat pre:=trace[x]; if pre>0 then ft[cv[x]]:=ft[cv[x]]+dt[1] else ft[cv[x]]:=ft[cv[x]]-dt[1]; x:=abs(pre); until x=n; End; Procedure Solve; Begin fl:=0; repeat Init; FindPath; if dt[1]>0 then IncFlow; fl:=fl+dt[1]; until dt[1]=0; End; Procedure WriteOutput; Begin Writeln(f2,fl); End; BEGIN OpenFiles; ReadInput; Trans; Solve; WriteOutput; CloseFiles; END.
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> #define fi first #define se second #define PB push_back #define MP make_pair #define ep 0.00001 #define oo 1111111111 #define mod 1000000007 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define rep(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) //#define g 9.81 double const PI=4*atan(1.0); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef long long ll; void OPEN(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); } // Dinic #define maxn 5011 #define maxe 200011 struct Dinic{ int s, t, E, adj[maxe], cap[maxe], flow[maxe], next[maxe], last[maxn], que[maxn], level[maxn], run[maxn]; void init(int _s, int _t){ s = _s; t = _t; E = 0; memset(last, -1, sizeof(last)); } void add(int u, int v, int c1, int c2){ adj[E] = v; cap[E] = c1; flow[E] = 0; next[E] = last[u]; last[u] = E++; adj[E] = u; cap[E] = c2; flow[E] = 0; next[E] = last[v]; last[v] = E++; } bool bfs(){ memset(level, -1, sizeof(level)); level[s] = 0; int size = 0; que[size++] = s; rep(i, size){ for(int u = que[i], e = last[u]; e != -1; e = next[e]){ int v = adj[e]; if(level[v] == -1 && flow[e] < cap[e]){ level[v] = level[u] + 1; que[size++] = v; } } } return level[t] != -1; } int dfs(int u, int bot){ if(u == t) return bot; for(int &e = run[u]; e != -1; e = next[e]){ int v = adj[e], delta; if(level[v] == level[u] + 1 && flow[e] < cap[e] && (delta = dfs(v, min(bot, cap[e] - flow[e]))) > 0){ flow[e] += delta; flow[e ^ 1] -= delta; return delta; } } return 0; } ll maxflow(){ ll total = 0; while(bfs()){ memcpy(run, last, sizeof(last)); for(int delta = dfs(s, oo); delta > 0; delta = dfs(s, oo)) total += delta; } return total; } } dinic; int main(){ //OPEN(); int n, u, v, cost; scanf("%d", &n); dinic.init(n, 1); while(scanf("%d %d %d", &u, &v, &cost) > 0){ dinic.add(u,v,cost,0); } printf("%lld\n",dinic.maxflow()); }
Code mẫu của skyvn97
#include<bits/stdc++.h> #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define REP(i,n) for (int i=0;i<(n);i=i+1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) using namespace std; const int INF=(int)1e9+7; class DinicFlow { private: vector<int> dist,head,q,work; vector<int> capa,flow,next,point; int n,m; public: DinicFlow() { n=0;m=0; } DinicFlow(int n) { this->n=n; this->m=0; dist=vector<int>(n+7); head=vector<int>(n+7,-1); q=vector<int>(n+7); work=vector<int>(n+7); } void addedge(int u,int v,int c1,int c2) { point.push_back(v);capa.push_back(c1);flow.push_back(0);next.push_back(head[u]);head[u]=m;m++; point.push_back(u);capa.push_back(c2);flow.push_back(0);next.push_back(head[v]);head[v]=m;m++; } bool bfs(int s,int t) { FOR(i,1,n) dist[i]=-1; int sz=1; q[0]=s;dist[s]=0; REP(x,sz) { int u=q[x]; for (int i=head[u];i>=0;i=next[i]) if (dist[point[i]]<0 && flow[i]<capa[i]) { dist[point[i]]=dist[u]+1; q[sz]=point[i]; sz++; } } return (dist[t]>=0); } int dfs(int s,int t,int f) { if (s==t) return (f); for (int &i=work[s];i>=0;i=next[i]) if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) { int d=dfs(point[i],t,min(f,capa[i]-flow[i])); if (d>0) { flow[i]+=d; flow[i^1]-=d; return (d); } } return (0); } int maxflow(int s,int t) { int totflow=0; while (bfs(s,t)) { FOR(i,1,n) work[i]=head[i]; while (true) { int d=dfs(s,t,INF); if (d<=0) break; totflow+=d; } } return (totflow); } }; int n; DinicFlow G; void process(void) { scanf("%d",&n); G=DinicFlow(n); int u,v,d; while (scanf("%d%d%d",&u,&v,&d)==3) G.addedge(u,v,d,0); cerr << 123 << endl; printf("%d",G.maxflow(n,1)); } int main(void) { #ifndef ONLINE_JUDGE freopen("tmp.txt","r",stdin); #endif process(); return 0; }
Comments