| 42 | }; |
| 43 | const ll INF=1e15; |
| 44 | struct Dinic { |
| 45 | const long long flow_inf = 1e18; |
| 46 | vector<FlowEdge> edges; |
| 47 | vector<vector<int>> adj; |
| 48 | int n, m = 0; |
| 49 | int s, t; |
| 50 | vector<int> level, ptr; |
| 51 | queue<int> q; |
| 52 | |
| 53 | Dinic(int n, int s, int t) : n(n), s(s), t(t) { |
| 54 | adj.resize(n); |
| 55 | level.resize(n); |
| 56 | ptr.resize(n); |
| 57 | } |
| 58 | |
| 59 | void add_edge(int v, int u, long long cap) { |
| 60 | edges.emplace_back(v, u, cap); |
| 61 | edges.emplace_back(u, v, 0); |
| 62 | adj[v].push_back(m); |
| 63 | adj[u].push_back(m + 1); |
| 64 | m += 2; |
| 65 | } |
| 66 | |
| 67 | bool bfs() { |
| 68 | while (!q.empty()) { |
| 69 | int v = q.front(); |
| 70 | q.pop(); |
| 71 | for (int id : adj[v]) { |
| 72 | if (edges[id].cap - edges[id].flow < 1) |
| 73 | continue; |
| 74 | if (level[edges[id].u] != -1) |
| 75 | continue; |
| 76 | level[edges[id].u] = level[v] + 1; |
| 77 | q.push(edges[id].u); |
| 78 | } |
| 79 | } |
| 80 | return level[t] != -1; |
| 81 | } |
| 82 | |
| 83 | long long dfs(int v, long long pushed) { |
| 84 | if (pushed == 0) |
| 85 | return 0; |
| 86 | if (v == t) |
| 87 | return pushed; |
| 88 | for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) { |
| 89 | int id = adj[v][cid]; |
| 90 | int u = edges[id].u; |
| 91 | if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1) |
| 92 | continue; |
| 93 | long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow)); |
| 94 | if (tr == 0) |
| 95 | continue; |
| 96 | edges[id].flow += tr; |
| 97 | edges[id ^ 1].flow -= tr; |
| 98 | return tr; |
| 99 | } |
| 100 | return 0; |
| 101 | } |
nothing calls this directly
no outgoing calls
no test coverage detected