fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. #define pp pair<int,int> >
  4. #define mp make_pair
  5. #define chk(a)	cout<<#a<<" : "<<a<<"\n";
  6. #define chk2(a,b) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<"\n";
  7. #define chk3(a,b,c) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<", "<<#c<<" : "<<c<<"\n";
  8. #define chk4(a,b,c,d) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<", "<<#c<<" : "<<c<<", "<<#d<<" : "<<d<<"\n";
  9. #define M 1000000007
  10. #define F first
  11. #define S second
  12. #define prev prevword
  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.     d[u] = 1000000042ll;
  92.     return 0;
  93. }
  94. int main()
  95. {
  96.     int m,i,u,v,c;
  97.     scanf("%d%d",&n,&m);
  98.  
  99.     for(i=0;i<m;i++)
  100.     {
  101.         scanf("%d%d%d",&u,&v,&c);
  102.         if(cap[u][v])
  103.         {
  104.             cap[u][v]+=c;
  105.             cap[v][u]+=c;
  106.         }
  107.         else if(u!=v)
  108.         {
  109.             gph[u].push_back(v);
  110.             gph[v].push_back(u);
  111.             cap[u][v]+=c;
  112.             cap[v][u]+=c;
  113.         }
  114.     }
  115.     ll ans=0;
  116.         while(bfs())
  117.         {
  118.             while(true)
  119.             {
  120.                 int df=dfs(1,1e15);
  121.  
  122.                 if(df==0)
  123.                     break;
  124.                 ans+=df;
  125.             }
  126.         }
  127.         printf("%lld\n",ans);
  128.         return 0;
  129. }
  130.  
Success #stdin #stdout 0s 395584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/LBl7V9
language:
C++14 (gcc 8.3)
created:
8 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!