fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define maxn 1005
  3. using namespace std;
  4. int n,m,s,t,f[maxn][maxn],dd[maxn],trc[maxn],c[maxn][maxn],res;
  5. vector<int> e[maxn];
  6. void findgraph()
  7. {
  8.     queue<int> q;
  9.     while(!q.empty()) q.pop();
  10.     dd[s]=1;
  11.     q.push(s);
  12.     while(!q.empty())
  13.     {
  14.         int u=q.front();
  15.         q.pop();
  16.         for (int i=0;i<(int)e[u].size();i++)
  17.         {
  18.             int v=e[u][i];
  19.             if (dd[v]) continue;
  20.             if (f[u][v]>=c[u][v]) continue;
  21.             trc[v]=u;
  22.             dd[v]=1;;
  23.             if (v==t)
  24.             {
  25.                 return;
  26.             }
  27.             q.push(v);
  28.         }
  29.     }
  30. }
  31. void incflow()
  32. {
  33.     int tmp=1000000000;
  34.     int v=t;
  35.     while(v!=s)
  36.     {
  37.         int u=trc[v];
  38.         tmp=min(tmp,c[u][v]-f[u][v]);
  39.         v=u;
  40.     }
  41.     v=t;
  42.     while(v!=s)
  43.     {
  44.         int u=trc[v];
  45.         f[u][v]+=tmp;
  46.         f[v][u]-=tmp;
  47.         v=u;
  48.     }
  49.     res+=tmp;
  50. }
  51. int main()
  52. {
  53.     //freopen("NKFLOW.inp","r",stdin);
  54.     ios::sync_with_stdio(0);
  55.     cin.tie(0);
  56.     cout.tie(0);
  57.     cin>>n>>m>>s>>t;
  58.     for (int i=1;i<=m;i++)
  59.     {
  60.         int u,v,val;
  61.         cin>>u>>v>>val;
  62.         c[u][v]=val;
  63.         e[u].push_back(v);
  64.         e[v].push_back(u);
  65.     }
  66.     while(1)
  67.     {
  68.         memset(dd,0,sizeof(dd));
  69.         memset(trc,0,sizeof(trc));
  70.         findgraph();
  71.         if (trc[t]==0) break;
  72.         incflow();
  73.     }
  74.     cout<<res;
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 10792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JNxZ0h
problem NKFLOW, based on SPOJ submission 19592114 (C++ 4.3.2), 2017-06-11 16:21:55
language:
C++ 4.3.2 (gcc-4.3.2)
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!