fork download
copy 
  1. #define pb push_back
  2. #define mp make_pair
  3. #define _(a,b) memset((a),(b),sizeof(a))
  4. #define sz(a) (int)(a).size()
  5.  
  6. const int maxn = 10100;
  7.  
  8. struct Edge
  9. {
  10.     int a, b, cap, flow, id;
  11. };
  12.  
  13. vector<Edge> e;
  14. vector<int> g[maxn];
  15. int S, T;
  16. int dist[maxn], ptr[maxn], q[maxn], sq;
  17.  
  18. void adde(int a, int b, int cap)
  19. {
  20. 	Edge t;
  21. 	t.a = a;
  22. 	t.b = b;
  23. 	t.id = sz(e);
  24. 	t.cap = cap;
  25. 	t.flow = 0;
  26. 	e.pb(t);
  27. 	g[t.a].pb(t.id);
  28.  
  29. 	swap(t.a, t.b);
  30. 	t.id++;
  31. 	t.cap = 0;
  32. 	e.pb(t);
  33. 	g[t.a].pb(t.id);
  34. }
  35.  
  36. bool bfs()
  37. {
  38. 	_(dist, -1);
  39. 	sq = 0;
  40. 	q[sq++] = S;
  41. 	dist[S] = 0;
  42. 	for (int i = 0; i < sq; i++)
  43. 	{
  44. 		int id = q[i];
  45. 		for (int j = 0; j < sz(g[id]); j++)
  46. 		{
  47. 			Edge &t = e[g[id][j]];
  48. 			if (dist[t.b] < 0 && t.flow < t.cap)
  49. 			{
  50. 				q[sq++] = t.b;
  51. 				dist[t.b] = dist[t.a] + 1;
  52. 			}
  53. 		}
  54. 	}
  55. 	return dist[T] >= 0;
  56. }
  57.  
  58. int dfs(int id, int exp)
  59. {
  60. 	if (exp == 0 || id == T)
  61. 		return exp;
  62. 	for (int &i = ptr[id]; i < sz(g[id]); i++)
  63. 	{
  64. 		Edge &t = e[g[id][i]];
  65. 		if (dist[t.b] == dist[t.a] + 1)
  66. 		{
  67. 			int push = dfs(t.b, min(exp, t.cap - t.flow));
  68. 			if (push)
  69. 			{
  70. 				t.flow += push;
  71. 				e[t.id ^ 1].flow -= push;
  72. 				return push;
  73. 			}
  74. 		}
  75. 	}
  76. 	return 0;
  77. }
  78.  
  79. int flow()
  80. {
  81. 	int ret = 0, x;
  82. 	while (bfs())
  83. 	{
  84. 		_(ptr, 0);
  85. 		while (x = dfs(S, INF))
  86. 			ret += x;
  87. 	}
  88. 	return ret;
  89. }
  90.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NpL8vs
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!