fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using vl = vector<ll>;
  5. #define FOR(i, a, b) for(ll i = (a); i < (b); i++)
  6. #define FORD(i, a, b) for(ll i = (b)-1; i >= (a); i--)
  7.  
  8. typedef vector<int> VI;
  9. typedef vector<VI> VVI;
  10. const ll INF = 1000000000000000000LL;
  11.  
  12. #define VEI(w,e) ((E[e].u == w) ? E[e].v : E[e].u)
  13. #define CAP(w,e) ((E[e].u == w) ? E[e].cap[0] - E[e].flow : E[e].cap[1] + E[e].flow)
  14. #define ADD(w,e,f) E[e].flow += ((E[e].u == w) ? (f) : (-(f)))
  15.  
  16. struct Edge { int u, v; ll cap[2], flow; };
  17.  
  18. VI d, act;
  19.  
  20. bool bfs(int s, int t, VVI& adj, vector<Edge>& E, ll lim) {
  21.   queue<int> Q;
  22.   d = VI(adj.size(), -1);
  23.   d[t] = 0;
  24.   Q.push(t);
  25.   while (not Q.empty() and d[s] == -1) {
  26.     int u = Q.front(); Q.pop();
  27.     for (int i = 0; i < int(adj[u].size()); ++i) {
  28.       int e = adj[u][i], v = VEI(u, e);
  29.       if (CAP(v, e) >= lim and d[v] == -1) {
  30.         d[v] = d[u] + 1;
  31.         Q.push(v);
  32.       }
  33.     }
  34.   }
  35.   return d[s] >= 0;
  36. }
  37.  
  38. bool dfs(int u,int t,ll bot,VVI& adj,vector<Edge>& E, ll lim) {
  39.   if (bot == 0) return false;
  40.   if (u == t) return true;
  41.   for (; act[u] < int(adj[u].size()); ++act[u]) {
  42.     int e = adj[u][act[u]];
  43.     if (CAP(u, e) >= lim and d[u] == d[VEI(u, e)] + 1) {
  44.       ll inc=dfs(VEI(u,e),t,min(bot,CAP(u,e)),adj,E,lim);
  45.       if (inc) {
  46.         ADD(u, e, lim);
  47.         return true;
  48.       }
  49.     }
  50.   }
  51.   return false;
  52. }
  53.  
  54. ll maxflow(int s, int t, VVI& adj, vector<Edge>& E) {
  55.   for (int i=0; i<int(E.size()); ++i) E[i].flow = 0;
  56.   ll flow = 0;
  57.   for(int lim = (1<<30); lim >= 1;) {
  58.     if(!bfs(s,t,adj,E, lim)) {
  59.       lim >>= 1;
  60.       continue;
  61.     }
  62.     act = VI(adj.size(), 0);
  63.     while (dfs(s,t,INF, adj, E, lim)) flow += lim;
  64.   }
  65.   return flow;
  66. }
  67.  
  68. void addEdge(int u, int v, VVI& adj, vector<Edge>& E, ll cap){
  69. 	Edge e;
  70. 	e.u = u;
  71. 	e.v = v;
  72. 	e.cap[0] = cap;
  73. 	e.cap[1] = cap;
  74. 	e.flow = 0;
  75. 	adj[u].push_back(E.size());
  76. 	adj[v].push_back(E.size());
  77. 	E.push_back(e);
  78. }
  79. int main() {
  80. 	int n, m;
  81. 	cin >> n >> m;
  82. 	vector<vector<int>>adj(n);
  83. 	vector<Edge> E;
  84. 	for(int i = 0; i < m; ++i) {
  85. 		int x,y,w;
  86. 		cin >> x >> y >> w;
  87. 		--x;--y;
  88. 		addEdge(x, y, adj, E, w);
  89. 	}
  90. 	cout << maxflow(0, n-1, adj ,E) << endl;
  91. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Xycg1M
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!