fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MODL 1000000000000000003
  3. #define pb push_back
  4. #define ll long long
  5. #define pii pair<int,int>
  6. #define mp make_pair
  7. using namespace std;
  8.  
  9. const int N=5000+9;
  10. int n,m;
  11. int par[N],lev[N];
  12. vector<int> adj[N];
  13. map<pii,ll> edg;
  14. ll dfs(int v,int p,ll mn){
  15.  
  16.     ll tosub=0;
  17.     for(auto u:adj[v])if(u!=p && lev[u]==lev[v]+1 && edg[mp(v,u)]>0){
  18.         ll nmn=min(1ll*mn,edg[mp(v,u)]);
  19.         if(u==n){
  20.             edg[mp(v,u)]-=nmn;
  21.             edg[mp(u,v)]+=nmn;
  22.             return nmn;
  23.         }
  24.         ll sub=dfs(u,v,nmn);
  25.         tosub+=sub;
  26.         if(sub){
  27.             edg[mp(v,u)]-=sub;
  28.             edg[mp(u,v)]+=sub;
  29.         }
  30.     }
  31.     return tosub;
  32.  
  33. }
  34. int main()
  35. { 
  36.  
  37.     ios::sync_with_stdio(false);cin.tie(0);
  38.     int tt=1;//cin>>tt;
  39.     while(tt--){
  40.         edg.clear();
  41.         cin>>n>>m;
  42.         for(int i=0;i<=n;i++){
  43.             adj[i].clear();
  44.         }
  45.         for(int i=0;i<m;i++){
  46.             int x,y,z;
  47.             cin>>x>>y>>z;
  48.             if(x==y)continue;
  49.             adj[x].pb(y);
  50.             adj[y].pb(x);
  51.             edg[mp(x,y)]+=z;
  52.             edg[mp(y,x)]+=z;
  53.  
  54.         }
  55.         ll ans=0;
  56.         while(1){
  57.  
  58.             // bfs to find augmenting path
  59.             queue<int> q;
  60.             for(int i=0;i<=n;i++){
  61.                 par[i]=lev[i]=-1;
  62.             }
  63.             par[1]=0;lev[1]=1;
  64.             q.push(1);
  65.             bool done=0;
  66.             while(!q.empty()){
  67.                 int v=q.front(); q.pop();
  68.                 for(auto u:adj[v])if((lev[u]==-1 || lev[u]>lev[v]) && par[u]==-1 && edg[mp(v,u)]>0){
  69.                     if(lev[u]==-1)lev[u]=lev[v]+1;
  70.                     par[u]=v;
  71.                     if(u==n){
  72.                         done=1;
  73.                         break;
  74.                     }
  75.                     q.push(u);
  76.                 }
  77.                 if(done)break;
  78.             }
  79.             if(done){
  80.                 // find blocking flow
  81.                 ll add=dfs(1,0,MODL);
  82.                 ans+=add;
  83.             } else break;
  84.  
  85.         }
  86.         cout<<ans<<endl;
  87.     }
  88.     return 0;
  89. }
Success #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/4kslYf
language:
C++14 (clang 8.0)
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!