SHARE
TWEET

Untitled

a guest May 20th, 2017 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m;
  5. typedef long long LL;
  6. namespace maxFlow{
  7.     const int MAXN = 5000;
  8.     int src, snk, n, nxt[MAXN+5], inf = 1.5e9, dist[MAXN+5];
  9.     struct edge{
  10.         int v, cap, opposite, flow;
  11.     };
  12.  
  13.     vector<edge>E[MAXN+5];
  14.  
  15.     void init(int _src, int _snk, int _n)
  16.     {
  17.         src = _src, snk = _snk, n = _n;
  18.     }
  19.  
  20.     void add(int u, int v, int cap)
  21.     {
  22.         E[u].push_back({v,cap,E[v].size(),0});
  23.         E[v].push_back({u,cap,E[u].size()-1,0});
  24.     }
  25.  
  26.     bool bfs()
  27.     {
  28.         memset(dist,-1,sizeof(dist));
  29.         queue<int>q;
  30.         dist[src] = 0;
  31.         q.push(src);
  32.         while(!q.empty())
  33.         {
  34.             int u = q.front();
  35.             q.pop();
  36.             for(int i = 0; i<E[u].size(); i++)
  37.             {
  38.                 if(E[u][i].cap > E[u][i].flow)
  39.                 {
  40.                     int v = E[u][i].v;
  41.                     if(dist[v] == -1)
  42.                     {
  43.                         dist[v] = dist[u] +1;
  44.                         q.push(v);
  45.                     }
  46.                 }
  47.             }
  48.         }
  49.         return dist[snk] != -1;
  50.     }
  51.  
  52.     int dfs(int u, int sentFlow)
  53.     {
  54.         if(u == snk)
  55.             return sentFlow;
  56.         for(; nxt[u]<E[u].size(); nxt[u]++)
  57.         {
  58.             int v = E[u][nxt[u]].v;
  59.             int c = E[u][nxt[u]].cap;
  60.             int f = E[u][nxt[u]].flow;
  61.             int opposite = E[u][nxt[u]].opposite;
  62.             if(dist[v] == dist[u]+1 && c > f)
  63.             {
  64.                 int tmp = dfs(v,min(sentFlow,c-f));
  65.                 if(tmp)
  66.                 {
  67.                     E[u][nxt[u]].flow += tmp;
  68.                     E[v][opposite].flow -= tmp;
  69.                     return tmp;
  70.                 }
  71.             }
  72.         }
  73.         return 0;
  74.     }
  75.  
  76.     LL dinitz()
  77.     {
  78.         LL totalFlow = 0;
  79.         while(bfs())
  80.         {
  81.             memset(nxt,0,sizeof(nxt));
  82.             int sentFlow;
  83.             while(sentFlow = dfs(src,inf))
  84.                 totalFlow += sentFlow;
  85.         }
  86.         return totalFlow;
  87.     }
  88.  
  89. }
  90.  
  91. int main()
  92. {
  93. //    freopen("in.txt", "r", stdin);
  94.     int i, j, u, v, w;
  95.     scanf("%d %d",&n,&m);
  96.     maxFlow::init(1,n,n);
  97.     for(int i = 1; i<=m; i++)
  98.     {
  99.         scanf("%d %d %d",&u,&v,&w);
  100.         if(u == v)
  101.             continue;
  102.         maxFlow::add(u,v,w);
  103.     }
  104.     printf("%lld\n",maxFlow::dinitz());
  105. }
RAW Paste Data
Top