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. 			flo -= f;
  66. 			fl += f;
  67. 			//return f;
  68. 		}
  69.  
  70. 	}
  71. 	dist[v] = INT_MAX;
  72. 	return fl;
  73. }
  74.  
  75. long long max_flow(int source, int sink)
  76. {
  77. 	long long flo = 0, f;
  78. 	while(bfs(source, sink))
  79. 	{
  80. 		f = dinic(source,sink,LONG_LONG_MAX);
  81. 		flo += f;
  82. 		if(f == 0)
  83. 			break;
  84. 	}
  85. 	return flo;
  86.  
  87. }
  88.  
  89. int main()
  90. {
  91. 	ios_base::sync_with_stdio(false);
  92. 	cin.tie(0);
  93.  
  94. 	int m;
  95. 	cin>>n>>m;
  96. 	int u,v,w;
  97.  
  98. 	for(int i=0;i<m;i++)
  99. 	{
  100. 		cin>>u>>v>>w;
  101. 		u--;
  102. 		v--;
  103. 		if (cap[u][v])
  104. 		{
  105. 			cap[u][v] += w;
  106. 			cap[v][u] += w;
  107. 		}
  108. 		else
  109. 		{
  110. 			cap[u][v] += w;
  111. 			cap[v][u] += w;
  112. 			graph[v].push_back(u);
  113. 			graph[u].push_back(v);
  114. 		}
  115. 	}
  116. 	cout<<max_flow(0, n-1)<<endl;
  117. } 
  118.  
Runtime error #stdin #stdout 0s 408128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J4BASW
problem FASTFLOW, based on SPOJ submission 19725605 (CPP14), 2017-07-03 15:26:45
language:
C++14 (gcc 8.3)
created:
6 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!