daily pastebin goal
2%
SHARE
TWEET

Untitled

a guest May 20th, 2017 60 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. #define mem(x,y)    memset(x,y,sizeof(x))
  5. int n, m;
  6. typedef long long LL;
  7. namespace maxFlow
  8. {
  9.     struct edge {
  10.     int a, b, f, c;
  11. };
  12.  
  13. const int inf = 1.5e9;
  14. const int MAXN = 5010;
  15.  
  16. int n, m;
  17. vector <edge> e;
  18. int pt[MAXN]; // very important performance trick
  19. vector <int> g[MAXN];
  20. long long flow = 0;
  21. queue <int> q;
  22. int d[MAXN];
  23. int lim;
  24. int s, t;
  25.  
  26. void add(int a, int b, int c) {
  27.     edge ed;
  28.  
  29.     //keep edges in vector: e[ind] - direct edge, e[ind ^ 1] - back edge
  30.  
  31.     ed.a = a; ed.b = b; ed.f = 0; ed.c = c;
  32.     g[a].push_back(e.size());
  33.     e.push_back(ed);
  34.  
  35.     ed.a = b; ed.b = a; ed.f = 0; ed.c = c;
  36.     g[b].push_back(e.size());
  37.     e.push_back(ed);
  38. }
  39.  
  40. bool bfs() {
  41.     for (int i = s; i <= t; i++)
  42.         d[i] = inf;
  43.     d[s] = 0;
  44.     q.push(s);
  45.     while (!q.empty() && d[t] == inf) {
  46.         int cur = q.front(); q.pop();
  47.         for (size_t i = 0; i < g[cur].size(); i++) {
  48.             int id = g[cur][i];
  49.             int to = e[id].b;
  50.  
  51.             //printf("cur = %d id = %d a = %d b = %d f = %d c = %d\n", cur, id, e[id].a, e[id].b, e[id].f, e[id].c);
  52.  
  53.             if (d[to] == inf && e[id].c - e[id].f >= lim) {
  54.                 d[to] = d[cur] + 1;
  55.                 q.push(to);
  56.             }
  57.         }
  58.     }
  59.     while (!q.empty())
  60.         q.pop();
  61.     return d[t] != inf;
  62. }
  63.  
  64. bool dfs(int v, int flow) {
  65.     if (flow == 0)
  66.         return false;
  67.     if (v == t) {
  68.         //cout << v << endl;
  69.         return true;
  70.     }
  71.     for (; pt[v] < g[v].size(); pt[v]++) {
  72.         int id = g[v][pt[v]];
  73.         int to = e[id].b;
  74.  
  75.         //printf("v = %d id = %d a = %d b = %d f = %d c = %d\n", v, id, e[id].a, e[id].b, e[id].f, e[id].c);
  76.  
  77.         if (d[to] == d[v] + 1 && e[id].c - e[id].f >= flow) {
  78.             int pushed = dfs(to, flow);
  79.             if (pushed) {
  80.                 e[id].f += flow;
  81.                 e[id ^ 1].f -= flow;
  82.                 return true;
  83.             }
  84.         }
  85.     }
  86.     return false;
  87. }
  88.  
  89. LL dinic() {
  90.     for (lim = (1 << 30); lim >= 1;) {
  91.         if (!bfs()) {
  92.             lim >>= 1;
  93.             continue;
  94.         }
  95.  
  96.         for (int i = s; i <= t; i++)
  97.             pt[i] = 0;
  98.  
  99.         int pushed;
  100.  
  101.         while (pushed = dfs(s, lim)) {
  102.             flow = flow + lim;
  103.         }
  104.  
  105.         //cout << flow << endl;
  106.     }
  107.     return flow;
  108. }
  109. }
  110.  
  111. int main()
  112. {
  113. //    freopen("in.txt", "r", stdin);
  114.     int i, j, u, v, w;
  115.     scanf("%d %d",&n,&m);
  116.     maxFlow::s = 1, maxFlow::t = n;
  117.     for(int i = 1; i<=m; i++)
  118.     {
  119.         scanf("%d %d %d",&u,&v,&w);
  120.         if(u == v)
  121.             continue;
  122.         maxFlow::add(u,v,w);
  123.     }
  124.     printf("%lld\n",maxFlow::dinic());
  125. }
RAW Paste Data
Top