网络流板子

 1 struct Dinic
 2 {
 3     int head[maxn], tot, cur[maxn];
 4     int dis[maxn];
 5     int s, e;
 6     queue<int>q;
 7 
 8     struct node
 9     {
10         int v, w;
11         int next;
12     }p[maxn];
13 
14     void init()
15     {
16         tot = 0;
17         memset(head, -1, sizeof head);
18     }
19 
20     void add(int u, int v, int w)
21     {
22         p[tot].v = v;
23         p[tot].w = w;
24         p[tot].next = head[u];
25         head[u] = tot++;
26     }
27 
28     void addEdge(int u, int v, int w)
29     {
30         add(u, v, w);
31         add(v, u, 0);
32     }
33 
34     bool bfs()
35     {
36         memset(dis, 0, sizeof dis);
37         while (!q.empty())   q.pop();
38         dis[s] = 1;
39         q.push(s);
40         while (!q.empty())
41         {
42             int x = q.front();
43             q.pop();
44             for (int i = head[x]; i != -1; i = p[i].next)
45             {
46                 int v = p[i].v, w = p[i].w;
47                 if (!dis[v] && w)
48                 {
49                     dis[v] = dis[x] + 1;
50                     q.push(v);
51                 }
52             }
53         }
54         if (dis[e])  return true;
55         return false;
56     }
57 
58     int dfs(int x, int W)
59     {
60         if (x == e || W == 0)  return W;
61         int res = 0;
62         for (int i = cur[x]; i != -1; i = p[i].next)
63         {
64             cur[x] = p[i].next;
65             int v = p[i].v, w = p[i].w;
66             if (dis[v] == dis[x] + 1)
67             {
68                 int f = dfs(v, min(w, W));
69                 p[i].w -= f;
70                 p[i ^ 1].w += f;
71                 W -= f;
72                 res += f;
73                 if (W == 0)    break;
74             }
75         }
76         return res;
77     }
78 
79     int getMaxFlow()
80     {
81         int ans = 0;
82         while (bfs())
83         {
84             for (int i = s; i <= e; ++i) cur[i] = head[i];
85             ans += dfs(s, inf);
86         }
87         return ans;
88     }
89 };