fork download
copy 
  1. /// MaxFlow with dinic by muoii
  2.  
  3. /// vn.spoj.com/problems/NKFLOW/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define tag "spoj"
  8. #define maxn 0
  9. #define maxc 0
  10. #define oo 1000000007
  11. #define mid ((l+r)>>1)
  12. #define meset(a,x) memset(a,x,sizeof(a))
  13. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  14. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  15. #define long long long
  16. struct network{
  17.  
  18.     int n;
  19.     ///data: E,adj,lev,cur
  20.     vector< vector<int> > adj;
  21.     vector<int> lev,cur;
  22.     struct edge{
  23.         int depa,dest;
  24.         long cap,flow;
  25.  
  26.         #define residual(e) ((e.flow<0?0:e.cap)-e.flow)
  27.         ///#define cost(e) ((e.flow<0?-1:1)*e.cost)
  28.     };
  29.     vector<edge> E;
  30.  
  31.     network(): n(0), E(0), adj(0), lev(0), cur(0) {};
  32.  
  33.     network(const int &N): n(N), E(0), adj(N+1), lev(N+1), cur(N+1) {};
  34.  
  35.     void add_edge(const int &u,const int &v,const int &cap,const bool &arcs)
  36.     {
  37.         adj[u].push_back(E.size());E.push_back({u,v,cap,0});
  38.         adj[v].push_back(E.size());E.push_back({v,u,arcs?0:cap,0});
  39.     }
  40.  
  41.     queue<int> Q;
  42.     bool augment(const int &s,const int &t)
  43.     {
  44.         fill(lev.begin(),lev.end(),-1);
  45.         lev[s]=0;
  46.         Q.push(s);
  47.  
  48.         int u;
  49.         edge e;
  50.         while(Q.size())
  51.         {
  52.             u=Q.front(),Q.pop();
  53.             cur[u]=0;
  54.             for(const int &ide: adj[u])
  55.             {
  56.                 e=E[ide];
  57.                 if(lev[e.dest]<0 && residual(e)>0)
  58.                 {
  59.                     lev[e.dest]=lev[u]+1;
  60.                     Q.push(e.dest);
  61.                 }
  62.             }
  63.         }
  64.         return lev[t]>0;
  65.     }
  66.  
  67.  
  68.     long augmenting(const int &u,const long &mincap,const int &sink)
  69.     {
  70.         if(u==sink || mincap==0) return mincap;
  71.  
  72.         long rep=0;
  73.  
  74.         int v,ide;
  75.         while(cur[u]<adj[u].size())
  76.         {
  77.             v=E[ide=adj[u][cur[u]]].dest;
  78.  
  79.             if(lev[u]+1==lev[v] && residual(E[ide])>0)
  80.                 if(rep=augmenting(v,min(mincap,residual(E[ide])),sink))
  81.                 {
  82.                     E[ide].flow+=rep;
  83.                     E[ide^1].flow-=rep;
  84.                     return rep;
  85.                 }
  86.             ++cur[u];
  87.         }
  88.         return rep;
  89.     }
  90.  
  91.     int MaxFlow(const int &s,const int &t)
  92.     {
  93.         int rep=0,delta;
  94.  
  95.         while(augment(s,t))
  96.         {
  97.             while(delta=augmenting(s,oo,t))
  98.                 rep+=delta;
  99.         }
  100.         return rep;
  101.     }
  102. };
  103. int main()
  104. {
  105.     #ifdef dmdd
  106.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  107.     #endif // dmdd
  108.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  109.  
  110.     int n,m,s,t;
  111.     cin>>n>>m>>s>>t;
  112.     network net(n);
  113.  
  114.     int u,v,w;
  115.     loop(m) cin>>u>>v>>w,net.add_edge(u,v,w,1);
  116.  
  117.     cout<<net.MaxFlow(s,t);
  118.     return 0;
  119. }
  120.  
  121.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
6 8 1 6
1 2 5
1 3 5
2 4 6
2 5 3
3 4 3
3 5 1
4 6 6
5 6 6
stdout
copy 
9
https://ideone.com/7nDNuq
language:
C++14 (gcc 8.3)
created:
6 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!