| 1 | #include "dinic.cpp" |
| 2 | bool same[MAXV]; |
| 3 | pair<vii, vvi> construct_gh_tree(flow_network &g) { |
| 4 | int n = g.n, v; |
| 5 | vii par(n, ii(0, 0)); vvi cap(n, vi(n, -1)); |
| 6 | rep(s,1,n) { |
| 7 | int l = 0, r = 0; |
| 8 | par[s].second = g.max_flow(s, par[s].first, false); |
| 9 | memset(d, 0, n * sizeof(int)); |
| 10 | memset(same, 0, n * sizeof(bool)); |
| 11 | d[q[r++] = s] = 1; |
| 12 | while (l < r) { |
| 13 | same[v = q[l++]] = true; |
| 14 | for (int i = g.head[v]; i != -1; i = g.e[i].nxt) |
| 15 | if (g.e[i].cap > 0 && d[g.e[i].v] == 0) |
| 16 | d[q[r++] = g.e[i].v] = 1; } |
| 17 | rep(i,s+1,n) |
| 18 | if (par[i].first == par[s].first && same[i]) |
| 19 | par[i].first = s; |
| 20 | g.reset(); } |
| 21 | rep(i,0,n) { |
| 22 | int mn = INF, cur = i; |
| 23 | while (true) { |
| 24 | cap[cur][i] = mn; |
| 25 | if (cur == 0) break; |
| 26 | mn = min(mn, par[cur].second), cur = par[cur].first; } } |
| 27 | return make_pair(par, cap); } |
| 28 | int compute_max_flow(int s, int t, const pair<vii, vvi> &gh) { |
| 29 | int cur = INF, at = s; |
| 30 | while (gh.second[at][t] == -1) |