【模板】【网络流】Dinic

  1 /*
  2 唐代杜荀鹤
  3 《小松》
  4 自小刺头深草里，而今渐觉出蓬蒿。
  5 时人不识凌云木，直待凌云始道高。
  6 */
  7 #include <iostream>
  8 #include <cstdio>
  9 #include <algorithm>
 10 #include <cstring>
 11 #include <vector>
 12 #include <utility>
 13 #include <iomanip>
 14 #include <string>
 15 #include <cmath>
 16 #include <queue>
 17 #include <assert.h>
 18 #include <map>
 19 #include <ctime>
 20 #include <cstdlib>
 21 #include <stack>
 22 #include <set> 
 23 #define LOCAL
 24 const int INF = 0x7fffffff;
 25 const int MAXN = 100000  + 10;
 26 const int maxnode = 20000 * 2 + 200000 * 20;
 27 const int MAXM = 50000 + 10;
 28 const int MAX = 100;
 29 using namespace std;
 30 struct Edge{
 31        int u, v, c, f;
 32        void init(int a, int b, int d, int e){
 33             u = a;v = b;
 34             c = d;f = e;
 35        }
 36 }edges[MAXM];
 37 int next[MAXN], M, cur[MAXN], vis[MAXN];
 38 int dist[MAXN], head[MAXN], n, m, sta, end;
 39 
 40 void addEdge(int u, int v, int c){
 41      edges[M].init(u, v, c, 0);M++;
 42      edges[M].init(v, u, 0, 0);//反向边 
 43      next[M - 1] = head[u];
 44      head[u] = M - 1;
 45      next[M] = head[v];
 46      head[v] = M++;
 47      return;
 48 }
 49 void init(){
 50      M = 0;//总边数 
 51      memset(head, -1, sizeof(head));
 52      scanf("%d%d", &n, &m);
 53      for (int i = 1; i <= m; i++){
 54          int u, v, c;
 55          scanf("%d%d%d", &u, &v, &c);
 56          addEdge(u, v, c);
 57      }
 58      sta = 1; 
 59      end = n;
 60 }
 61 bool bfs(){
 62      memset(vis, 0, sizeof(vis));
 63      queue<int>Q;
 64      dist[sta] = 0;
 65      vis[sta] = 1;
 66      Q.push(sta);
 67      while (!Q.empty()){
 68            int u = Q.front();
 69            Q.pop();
 70            for (int i = head[u]; i != -1;  i = next[i]){
 71                int e = i, v = edges[e].v;
 72                if (vis[v]) continue;
 73                if (edges[e].c > edges[e].f){
 74                   vis[v] = 1;
 75                   dist[v] = dist[u] + 1;
 76                   Q.push(v);
 77                }
 78            }
 79      }
 80      return vis[end];
 81 }
 82 int dfs(int x, int a){
 83     if (x == end || a == 0) return a;
 84     int flow = 0, f;
 85     if (cur[x] == -1) cur[x] = head[x];
 86     for (int &i = cur[x]; i != -1; i = next[i]){
 87         int e = i, v = edges[i].v;
 88         if (dist[v] == dist[x] + 1 && (f = dfs(v, min(edges[e].c - edges[e].f, a))) > 0){
 89            flow += f;
 90            a -= f;
 91            edges[e].f += f;
 92            edges[e ^ 1].f -= f;
 93            if (a == 0) break;
 94         }
 95     }
 96     return flow;
 97 }
 98 int Dinic(){
 99     int flow = 0;
100     while (bfs()){
101           memset(cur, -1, sizeof(cur));
102           flow += dfs(sta, INF);
103     }
104     return flow;
105 }
106 
107 int main(){
108    #ifdef LOCAL
109    freopen("data.txt", "r", stdin);
110    freopen("out.txt", "w", stdout);
111    #endif
112    init();
113    printf("%d", Dinic());
114    //printf("%d", (a == c));
115    return 0; 
116 }
View Code