fork download
copy 
  1.  
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <queue>
  7.  
  8. using namespace std;
  9.  
  10. const int inf = 1000 * 1000 * 1000;
  11.  
  12. typedef vector<int> vec;
  13. typedef vector<vec> graph;
  14.  
  15.  
  16. int main()
  17. {
  18. 	//input your graph
  19. 	int n = 6;
  20. 	graph c(n, vec(n));
  21.  
  22. 	c[0][1] = 11;
  23. 	c[0][2] = 11;
  24. 	c[1][3] = 4;
  25. 	c[1][4] = 8;
  26. 	c[1][2] = 3;
  27. 	c[2][4] = 9;
  28. 	c[3][5] = 10;
  29. 	c[4][3] = 6;
  30. 	c[4][5] = 10;
  31.  
  32. 	// Search wide (poisk v shirinu), searching lowest way
  33. 	graph f(n, vec(n));
  34.  
  35. 	for (;;)
  36. 	{
  37.  
  38. 		vec from(n, -1);
  39. 		queue<int> q;
  40.  
  41. 		q.push(0);
  42. 		from[0] = 0;
  43.  
  44. 		for (int cur; !q.empty();)
  45. 		{
  46. 			cur = q.front();
  47. 			q.pop();
  48. 			for (int v = 0; v < n; v++)
  49. 				if (from[v] == -1 && c[cur][v] - f[cur][v] > 0)
  50. 				{
  51. 					q.push(v);
  52. 					from[v] = cur;
  53. 				}
  54. 		}
  55.  
  56. 		if (from[n - 1] == -1)
  57. 			break;
  58.  
  59. 		int cf = inf;
  60.  
  61. 		//MaxFlow
  62.  
  63. 		for (int cur = n - 1; cur != 0; )
  64. 		{
  65. 			int prev = from[cur];
  66. 			cf = min(cf, c[prev][cur] - f[prev][cur]);
  67. 			cur = prev;
  68. 		}
  69.  
  70. 		for (int cur = n - 1; cur != 0; )
  71. 		{
  72. 			int prev = from[cur];
  73. 			f[prev][cur] += cf;
  74. 			f[cur][prev] -= cf;
  75. 			cur = prev;
  76. 		}
  77.  
  78. 	}
  79.  
  80. 	int MaxFlow = 0;
  81. 	for (int i = 0; i < n; i++)
  82. 		if (c[0][i] != 0)
  83. 			MaxFlow += f[0][i];
  84.  
  85. 	cout << MaxFlow << endl;
  86. }
  87.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
20
https://ideone.com/tJcNZD
language:
C++ (gcc 8.3)
created:
5 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!