fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #define ll long long
  4. #include <vector>
  5. #define INF (1000*1000*1000+1)
  6. using namespace std;
  7. struct edge{
  8. 	ll u1;
  9. 	ll u2;
  10. 	ll cap;
  11. 	ll flow;
  12.  
  13. };
  14.  
  15.  
  16. bool bfs(vector<vector<ll> > adj,vector<ll> &level,vector<edge> elist,ll src,ll sink){
  17. 	ll n=adj.size()-1;
  18. 	for(ll i=1;i<=n;i++)
  19. 	level[i]=-1;
  20. 	queue<ll> q;
  21. 	q.push(src);
  22. 	level[src]=0;
  23.  
  24. 	while(!q.empty()){
  25. 		ll k=q.size();
  26. 		for(ll i=0;i<k;i++){
  27. 			ll cur=q.front();
  28. 			q.pop();
  29. 			for(auto x:adj[cur]){
  30. 				ll v1=elist[x].u2;
  31. 				if(level[v1]==-1 && elist[x].flow<elist[x].cap){
  32. 					level[v1]=level[cur]+1;
  33. 					q.push(v1);
  34. 				}
  35. 			}
  36. 		}
  37. 	}
  38. 	if(level[sink]==-1)
  39. 	return 0;
  40. 	return 1;
  41. }
  42. ll block(vector<vector<ll> > adj,vector<ll> level,ll src,ll sink,vector<edge> &elist,ll pushed,vector<ll> &start){
  43. 	//cout<<src<<" "<<pushed<<endl;
  44.  
  45. 	if(pushed==0)
  46. 	return 0;
  47. 	if(src==sink)
  48. 	return pushed;
  49. 	for( ;start[src]<adj[src].size();start[src]++){
  50. 		ll v1=elist[adj[src][start[src]]].u2;
  51.  
  52.  
  53. 		ll cap=elist[adj[src][start[src]]].cap;
  54. 		ll flow=elist[adj[src][start[src]]].flow;
  55.  
  56.  
  57. 		if(level[v1]==level[src]+1 && flow<cap){
  58. 			//cout<<"h"<<src<<" "<<v1<<" "<<cap<<" "<<flow<<endl;
  59. 			ll temp=block(adj,level,v1,sink,elist,min(pushed,cap-flow),start);
  60. 			if(temp>0){
  61. 				elist[adj[src][start[src]]].flow+=temp;
  62.  
  63. 				elist[adj[src][start[src]]^1].flow-=temp;
  64.  
  65.  
  66. 				return temp;
  67. 			}
  68. 		}
  69.  
  70.  
  71. 	}
  72. 	return 0;
  73. }
  74.  
  75. ll dinc(vector<vector<ll> > adj,vector<edge> &elist,ll src,ll sink){
  76. 	ll ans=0;
  77. 	ll n=adj.size()-1;
  78. 	vector<ll> level(n+1);
  79. 	while(bfs(adj,level,elist,src,sink)){
  80.  
  81. 		ll temp=0;
  82. 		vector<ll> start(n+1);
  83. 		for(ll i=1;i<=n;i++)
  84. 		start[i]=0;
  85. 		ll pushed=INF;
  86.  
  87. 		while((temp=block(adj,level,src,sink,elist,pushed,start))!=0){
  88.  
  89. 			ans+=temp;
  90. 		}
  91.  
  92.  
  93.  
  94. 	}
  95. 	return ans;
  96. }
  97.  
  98. int main() {
  99. 	// your code goes here
  100. 	ll n,m;
  101. 	scanf("%lld %lld",&n,&m);
  102. 	ll isedge[n+1][n+1];
  103. 	for(ll i=1;i<=n;i++){
  104. 		for(ll j=1;j<=n;j++)
  105. 		isedge[i][j]=-1;
  106. 	}
  107. 	vector<edge> elist;
  108. 	vector<vector<ll> >adj(n+1);
  109. 	ll cur=0;
  110. 	for(ll i=1;i<=m;i++){
  111. 		ll a,b,c;
  112. 		scanf("%lld %lld %lld",&a,&b,&c);
  113. 		if(a==b)
  114. 		continue;
  115. 		if(isedge[a][b]==-1){
  116. 			isedge[a][b]=cur;
  117. 			isedge[b][a]=cur+1;
  118. 			edge e;
  119. 			e.u1=a;
  120. 			e.u2=b;
  121. 			e.cap=c;
  122. 			e.flow=0;
  123. 			elist.push_back(e);
  124. 			e.u1=b;
  125. 			e.u2=a;
  126. 			e.cap=c;
  127. 			e.flow=0;
  128. 			elist.push_back(e);
  129. 			adj[a].push_back(cur);
  130. 			adj[b].push_back(cur+1);
  131. 			cur+=2;
  132. 		}
  133. 		else{
  134. 			elist[isedge[a][b]].cap+=c;
  135. 			elist[isedge[b][a]].cap+=c;
  136. 		}
  137. 	}
  138.  
  139. 	ll ans=dinc(adj,elist,1,n);
  140. 	printf("%lld",ans);
  141.  
  142. 	return 0;
  143. }
Success #stdin #stdout 0s 4772KB
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/KPUELZ
problem FASTFLOW, based on SPOJ submission 27382897 (CPP14), 2021-02-03 10:04:08
language:
C++14 (gcc 8.3)
created:
3 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!