fork(4) download
copy 
  1. #include<bits/stdc++.h>
  2. #define maxn 1005
  3. using namespace std;
  4. int n,m,res,s,t;
  5. struct data
  6. {
  7.             int v,f,c;
  8. };
  9. vector <data> e;
  10. vector<int>g[maxn];
  11. int dd[maxn],cnt,d[maxn],pos[maxn];
  12. bool bfs()
  13. {
  14.             queue<int> q;
  15.             dd[s]=++cnt;
  16.             while(!q.empty()) q.pop();
  17.             q.push(s);
  18.             while(!q.empty())
  19.             {
  20.                         int u=q.front();
  21.                         pos[u]=0;
  22.                         q.pop();
  23.                         for (int i=0; i<(int)g[u].size(); ++i)
  24.                         {
  25.                                     int id=g[u][i];
  26.                                     int v=e[id].v;
  27.                                     if (e[id].f==e[id].c||dd[v]==cnt) continue;
  28.                                     dd[v]=cnt;
  29.                                     d[v]=d[u]+1;
  30.                                     q.push(v);
  31.                         }
  32.             }
  33.             return dd[t]==cnt;
  34. }
  35. int dfs(int u,int low)
  36. {
  37.             if (u==t||low==0) return low;
  38.             for (; pos[u]<g[u].size(); ++pos[u])
  39.             {
  40.                         int id=g[u][pos[u]];
  41.                         int v=e[id].v;
  42.                         if (d[v]!=d[u]+1||e[id].f==e[id].c) continue;
  43.                         int get=dfs(v,min(low,e[id].c-e[id].f));
  44.                         if (get)
  45.                         {
  46.                                     e[id].f+=get;
  47.                                     e[id^1].f-=get;
  48.                                     return get;
  49.                         }
  50.             }
  51.             return 0;
  52. }
  53. int main()
  54. {
  55.             //freopen("NKFLOW.inp","r",stdin);
  56.             ios::sync_with_stdio(0);
  57.             cin.tie(0);
  58.             cout.tie(0);
  59.             cin>>n>>m>>s>>t;
  60.             for (int i=1; i<=m; ++i)
  61.             {
  62.                         int u,v,w;
  63.                         cin>>u>>v>>w;
  64.                         g[u].push_back(e.size());
  65.                         data x;
  66.                         x.v=v;
  67.                         x.c=w;
  68.                         x.f=0;
  69.                         e.push_back(x);
  70.                         g[v].push_back(e.size());
  71.                         x.v=u;
  72.                         x.c=0;
  73.                         x.f=0;
  74.                         e.push_back(x);
  75.             }
  76.             while(bfs())
  77.             {
  78.                         while(int x=dfs(s,10000000))
  79.                         {
  80.                                     res+=x;
  81.                         }
  82.             }
  83.             cout<<res;
  84.             return 0;
  85. }
  86.  
Time limit exceeded #stdin #stdout 5s 16104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DGrZT7
problem NKFLOW, based on SPOJ submission 19932767 (CPP), 2017-08-08 05:11:26
language:
C++ (gcc 8.3)
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!