fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const int MAXN = 5001;
  6. const int INF = 1000000000;
  7. vector<int> g[MAXN] ;
  8.  
  9. int n, m, c[MAXN][MAXN], f[MAXN][MAXN], s, t, d[MAXN], ptr[MAXN], q[MAXN];
  10.  
  11. bool bfs() {
  12.         queue<int> q ;
  13. 	memset (d, -1, sizeof d);
  14. 	q.push(s) ;
  15. 	d[s] = 0 ;
  16. 	while(!q.empty())
  17.         {
  18.                 int v = q.front() ;
  19.                 q.pop() ;
  20.                 for(int i = 0; i < g[v].size(); i++)
  21.                 {
  22.                         int to = g[v][i] ;
  23.                         if(d[to] == -1 and f[v][to] < c[v][to])
  24.                         {
  25.                                 q.push(to) ;
  26.                                 d[to] = d[v] + 1 ;
  27.                         }
  28.                 }
  29.         }
  30. 	return d[t] != -1 ;
  31. }
  32.  
  33. int dfs (int v, int flow) {
  34. 	if (!flow)  return 0;
  35. 	if (v == t)  return flow;
  36. 	for (int & to=ptr[v]; to <= n; ++to) {
  37. 		if (d[to] != d[v] + 1)  continue;
  38. 		int pushed = dfs (to, min (flow, c[v][to] - f[v][to]));
  39. 		if (pushed) {
  40. 			f[v][to] += pushed;
  41. 			f[to][v] -= pushed;
  42. 			return pushed;
  43. 		}
  44. 	}
  45. 	return 0;
  46. }
  47.  
  48. ll dinic() {
  49. 	ll flow = 0;
  50. 	for (;;) {
  51. 		if (!bfs())  break;
  52. 		memset (ptr, 0, n * sizeof ptr[0]);
  53. 		while (int pushed = dfs (s, INF))
  54. 			flow += (1LL * pushed);
  55. 	}
  56. 	return flow;
  57. }
  58.  
  59. int main() {
  60.     //ifstream cin("input.txt") ;
  61.     //ofstream cout("output.txt") ;
  62.     cin.sync_with_stdio(false) ;
  63.     cin.tie(NULL) ;
  64.     cin >> n >> m ;
  65.     while(m--)
  66.     {
  67.             int n1, n2, cap;
  68.             cin >> n1 >> n2 >> cap ;
  69.             if(n1 == n2)
  70.                 continue ;
  71.             g[n1].push_back(n2) ;
  72.             g[n2].push_back(n1) ;
  73.             c[n1][n2] += cap ;
  74.             c[n2][n1] += cap ;
  75.     }
  76.     s = 1, t = n ;
  77.     cout << dinic() ;
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0s 211648KB
comments (?)
stdin
copy 
4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3
stdout
copy 
5
https://ideone.com/5kgz5r
language:
C++14 (gcc 8.3)
created:
6 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!