| 1 | #define MAXV 2000 |
| 2 | int q[MAXV], d[MAXV]; |
| 3 | struct flow_network { |
| 4 | struct edge { int v, nxt, cap; |
| 5 | edge(int _v, int _cap, int _nxt) |
| 6 | : v(_v), nxt(_nxt), cap(_cap) { } }; |
| 7 | int n, *head, *curh; vector<edge> e, e_store; |
| 8 | flow_network(int _n) : n(_n) { |
| 9 | curh = new int[n]; |
| 10 | memset(head = new int[n], -1, n*sizeof(int)); } |
| 11 | void reset() { e = e_store; } |
| 12 | void add_edge(int u, int v, int uv, int vu=0) { |
| 13 | e.push_back(edge(v,uv,head[u])); head[u]=(int)size(e)-1; |
| 14 | e.push_back(edge(u,vu,head[v])); head[v]=(int)size(e)-1;} |
| 15 | int augment(int v, int t, int f) { |
| 16 | if (v == t) return f; |
| 17 | for (int &i = curh[v], ret; i != -1; i = e[i].nxt) |
| 18 | if (e[i].cap > 0 && d[e[i].v] + 1 == d[v]) |
| 19 | if ((ret = augment(e[i].v, t, min(f, e[i].cap))) > 0) |
| 20 | return (e[i].cap -= ret, e[i^1].cap += ret, ret); |
| 21 | return 0; } |
| 22 | int max_flow(int s, int t, bool res=true) { |
| 23 | e_store = e; |
| 24 | int l, r, f = 0, x; |
| 25 | while (true) { |
| 26 | memset(d, -1, n*sizeof(int)); |
| 27 | l = r = 0, d[q[r++] = t] = 0; |
| 28 | while (l < r) |
| 29 | for (int v = q[l++], i = head[v]; i != -1; i=e[i].nxt) |
| 30 | if (e[i^1].cap > 0 && d[e[i].v] == -1) |
| 31 | d[q[r++] = e[i].v] = d[v]+1; |
| 32 | if (d[s] == -1) break; |
| 33 | memcpy(curh, head, n * sizeof(int)); |
| 34 | while ((x = augment(s, t, INF)) != 0) f += x; } |
| 35 | if (res) reset(); |
| 36 | return f; } }; |
| 37 | // vim: cc=60 ts=2 sts=2 sw=2: |