This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../maxflow/fordfulkerson.cpp" #undef call_from_test int main(){ cin.tie(0); ios::sync_with_stdio(0); int V,E; cin>>V>>E; FordFulkerson<int, true> G(V); for(int i=0;i<E;i++){ int u,v,c; cin>>u>>v>>c; G.add_edge(u,v,c); } cout<<G.flow(0,V-1)<<endl; return 0; }
#line 1 "test/aoj/GRL_6_A.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "maxflow/fordfulkerson.cpp" #line 3 "maxflow/fordfulkerson.cpp" using namespace std; #endif //BEGIN CUT HERE // O(F E) template<typename Flow, bool directed> struct FordFulkerson{ struct Edge{ int dst; Flow cap; int rev; Edge(int dst,Flow cap,int rev):dst(dst),cap(cap),rev(rev){} }; vector< vector<Edge> > G; vector<int> used; FordFulkerson(int n):G(n),used(n){} int add_edge(int src,int dst,Flow cap){ int e=G[src].size(); int r=(src==dst?e+1:G[dst].size()); G[src].emplace_back(dst,cap,r); G[dst].emplace_back(src,directed?0:cap,e); return e; } Flow dfs(int v,int t,Flow f){ if(v==t) return f; used[v]=true; for(Edge &e:G[v]){ if(used[e.dst] or e.cap==0) continue; Flow d=dfs(e.dst,t,min(f,e.cap)); if(d==0) continue; e.cap-=d; G[e.dst][e.rev].cap+=d; return d; } return 0; } Flow flow(int s,int t,Flow lim){ Flow res=0; while(1){ fill(used.begin(),used.end(),0); Flow f=dfs(s,t,lim); if(f==0) break; res+=f; lim-=f; } return res; } Flow flow(int s,int t){ return flow(s,t,numeric_limits<Flow>::max()/2); } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/aoj/GRL_6_A.test.cpp" #undef call_from_test int main(){ cin.tie(0); ios::sync_with_stdio(0); int V,E; cin>>V>>E; FordFulkerson<int, true> G(V); for(int i=0;i<E;i++){ int u,v,c; cin>>u>>v>>c; G.add_edge(u,v,c); } cout<<G.flow(0,V-1)<<endl; return 0; }