wind的网络流神模板--【秒过。。】【网络流】
2020-12-13 15:48
标签：style blog http color ar os for sp div wind的网络流神模板--【秒过。。】【网络流】 标签：style blog http color ar os for sp div 原文地址：http://www.cnblogs.com/zhanzhao/p/4076994.html
1 const int maxn = 405;
2 const int maxm = maxn * maxn;
3 const int inf = 1000000000;
4
5 class Dinic {
6 public :
7 struct Node {
8 int u, v, f, next;
9 }e[maxm];
10
11 int head[maxn], p, lev[maxn], cur[maxn];
12 int que[maxm];
13
14 void init() {
15 p = 0;
16 memset(head, -1, sizeof(head));
17 }
18
19 void add(int u, int v, int f) {
20 e[p].u = u; e[p].v = v; e[p].f = f; e[p].next = head[u]; head[u] = p++;
21 e[p].u = v; e[p].v = u; e[p].f = 0; e[p].next = head[v]; head[v] = p++;
22 }
23
24 bool bfs(int s, int t) {
25 int u, v, qin = 0, qout = 0;
26 memset(lev, 0, sizeof(lev)); lev[s] = 1; que[qin++] = s;
27 while(qout != qin) {
28 u = que[qout++];
29 for(int i = head[u]; i != -1; i = e[i].next) {
30 if(e[i].f > 0 && !lev[v = e[i].v]) {
31 lev[v] = lev[u] + 1, que[qin++] = v;
32 if(v == t) return 1;
33 }
34 }
35 }
36 return 0;
37 }
38
39 int dfs(int s, int t) {
40 int i, f, qin, u, k;
41 int flow = 0;
42 while(bfs(s, t)) {
43 memcpy(cur, head, sizeof(head));
44 u = s, qin = 0;
45 while(1) {
46 if(u == t) {
47 for(k = 0, f = inf; k )
48 if(e[que[k]].f k]].f;
49 for(k = 0; k )
50 e[que[k]].f -= f, e[que[k]^1].f += f;
51 flow += f, u = e[que[qin = i]].u;
52 }
53 for(i = cur[u]; cur[u] != -1; i = cur[u] = e[cur[u]].next)
54 if(e[i].f > 0 && lev[u] + 1 == lev[e[i].v]) break;
55 if(cur[u] != -1)
56 que[qin++] = cur[u], u = e[cur[u]].v;
57 else {
58 if(qin == 0) break;
59 lev[u] = -1, u = e[que[--qin]].u;
60 }
61 }
62 }
63 return flow;
64 }
65 };
66
67 Dinic g;