fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> dist;
  5. vector<int> ptr;
  6. vector< vector<int> > graph(5000);
  7. long long cap[5009][5009];
  8. long long flow[5009][5009];
  9.  
  10. int n;
  11.  
  12. bool bfs(int source, int sink)
  13. {
  14. 	queue<int> q;
  15. 	vector<int> visited(n,false);
  16.  
  17. 	int i,j,v;
  18. 	dist.resize(n);
  19. 	ptr.resize(n);
  20.  
  21. 	for(i=0;i<n;i++)
  22. 		dist[i]= ptr[i]= 0;
  23.  
  24. 	q.push(source);
  25. 	visited[source]=true;
  26. 	while(!q.empty())
  27. 	{
  28. 		v = q.front();
  29. 		q.pop();
  30. 		for (i=0;i<graph[v].size();i++)
  31. 		{
  32. 			j = graph[v][i];
  33. 			if (!visited[j] && cap[v][j] - flow[v][j]>0)
  34. 			{
  35. 				q.push(j);
  36. 				dist[j] = dist[v]+1;
  37. 				visited[j] = true;
  38. 			}
  39. 		}
  40. 	}
  41.  
  42. 	if(visited[sink])
  43. 		return true;
  44. 	return false;
  45. }
  46.  
  47. long long dinic(int v, int sink, long long flo)
  48. {
  49. 	if (v == sink || flo == 0)
  50. 		return flo;
  51.  
  52. 	long long fl = 0;
  53. 	int j;
  54. 	for(;ptr[v]<graph[v].size();++ptr[v])
  55. 	{
  56. 		j = graph[v][ptr[v]];
  57. 		if(cap[v][j] - flow[v][j] >0 && dist[j] == dist[v]+1)
  58. 		{
  59.  
  60. 			long long f = dinic(j, sink, min(flo,cap[v][j] - flow[v][j]));
  61. 			if(f == 0)
  62. 				continue;
  63. 			flow[v][j] += f;
  64. 			flow[j][v] -= f;
  65. 			return f;
  66. 		}
  67.  
  68. 	}
  69. 	dist[v] = INT_MAX;
  70. 	return 0;
  71. }
  72.  
  73. long long max_flow(int source, int sink)
  74. {
  75. 	long long flo = 0, f;
  76. 	while(bfs(source, sink))
  77. 	{
  78. 		f = dinic(source,sink,LONG_LONG_MAX);
  79. 		flo += f;
  80. 		if(f == 0)
  81. 			break;
  82. 	}
  83. 	return flo;
  84.  
  85. }
  86.  
  87. int main()
  88. {
  89. 	ios_base::sync_with_stdio(false);
  90. 	cin.tie(0);
  91.  
  92. 	int m;
  93. 	cin>>n>>m;
  94. 	int u,v,w;
  95.  
  96. 	for(int i=0;i<m;i++)
  97. 	{
  98. 		cin>>u>>v>>w;
  99. 		u--;
  100. 		v--;
  101. 		if (cap[u][v])
  102. 		{
  103. 			cap[u][v] += w;
  104. 			cap[v][u] += w;
  105. 		}
  106. 		else
  107. 		{
  108. 			cap[u][v] += w;
  109. 			cap[v][u] += w;
  110. 			graph[v].push_back(u);
  111. 			graph[u].push_back(v);
  112. 		}
  113. 	}
  114. 	cout<<max_flow(0, n-1)<<endl;
  115. } 
  116.  
Runtime error #stdin #stdout 0s 408128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7FFYRy
language:
C++14 (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!