fork(1) download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. #define ll long long int
  4. #define pp pair<int,int> >
  5. #define mp make_pair
  6. #define chk(a)	cout<<#a<<" : "<<a<<"\n";
  7. #define chk2(a,b) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<"\n";
  8. #define chk3(a,b,c) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<", "<<#c<<" : "<<c<<"\n";
  9. #define chk4(a,b,c,d) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<", "<<#c<<" : "<<c<<", "<<#d<<" : "<<d<<"\n";
  10. #define M 1000000007
  11. #define F first
  12. #define S second
  13. using namespace std;
  14. int n;
  15. ll powe(ll a,ll b)
  16. {
  17. 	ll ans=1;
  18. 	while(b)
  19. 	{
  20. 		if(b&1)
  21. 			ans=(ans*a)%M;
  22. 		b=b/2;
  23. 		a=(a*a)%M;
  24. 	}
  25. 	return ans;
  26. }
  27. ll mini(ll a,ll b)
  28. {
  29.     if(a<b)
  30.         return a;
  31.         return b;
  32. }
  33. ll gcde(ll a,ll b)
  34. {
  35. 	if(b==0)
  36. 		return a;
  37. 	return gcde(b,a%b);
  38. }
  39.  
  40. ll cap[5009][5009];
  41. ll flow[5009][5009];
  42. int d[5009],prev[5009];
  43. vector<int> gph[5009];
  44. int q[5009];
  45. bool bfs()
  46. {
  47.     int u=1;
  48.     memset(d,-1,sizeof(d));
  49.  
  50.     d[1]=0;
  51.     prev[u]=-1;
  52.     int sx,ex;
  53.     sx=0;ex=-1;
  54.     q[++ex]=1;
  55.     while(sx<=ex and sx!=-1)
  56.     {
  57.         u=q[sx++];
  58.         for(int i=0;i<gph[u].size();i++)
  59.         {
  60.             int to=gph[u][i];
  61.             if(d[to]==-1 and cap[u][to]-flow[u][to]>0)
  62.             {
  63.                 d[to]=d[u]+1;
  64.                 q[++ex]=to;
  65.             }
  66.         }
  67.     }
  68.     return (d[n]!=-1);
  69. }
  70.  
  71. ll dfs(int u,ll fl)
  72. {
  73.     if(u==n)
  74.         return fl;
  75.     for(int i=0;i<gph[u].size();i++)
  76.     {
  77.         int to=gph[u][i];
  78.         if(cap[u][to]-flow[u][to]>0 and d[to]==d[u]+1)
  79.         {
  80.             fl=mini(fl,cap[u][to]-flow[u][to]);
  81.             int df=dfs(to,fl);
  82.             if(df>0)
  83.             {
  84.  
  85.                 flow[u][to]+=df;
  86.                 flow[to][u]-=df;
  87.                 return df;
  88.             }
  89.         }
  90.     }
  91.     return 0;
  92. }
  93. int main()
  94. {
  95.     int m,i,u,v,c;
  96.     scanf("%d%d",&n,&m);
  97.  
  98.     for(i=0;i<m;i++)
  99.     {
  100.         scanf("%d%d%d",&u,&v,&c);
  101.         if(cap[u][v])
  102.         {
  103.             cap[u][v]+=c;
  104.             cap[v][u]+=c;
  105.         }
  106.         else if(u!=v)
  107.         {
  108.             gph[u].push_back(v);
  109.             gph[v].push_back(u);
  110.             cap[u][v]+=c;
  111.             cap[v][u]+=c;
  112.         }
  113.     }
  114.     ll ans=0;
  115.         while(bfs())
  116.         {
  117.             while(true)
  118.             {
  119.                 int df=dfs(1,1e15);
  120.  
  121.                 if(df==0)
  122.                     break;
  123.                 ans+=df;
  124.             }
  125.         }
  126.         printf("%lld\n",ans);
  127.         return 0;
  128. }
  129.  
Success #stdin #stdout 0s 395648KB
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/WhzEaw
language:
C++ (gcc 8.3)
created:
8 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!