最大流
Dinic 解
使用 \(\tt Dinic\) 算法，理论最坏复杂度为 \(\mathcal O(N^2M)\) ，例题范围：\(N=1200,\ m=5\times 10^3\) 。一般步骤：\(\tt BFS\) 建立分层图，无回溯 \(\tt DFS\) 寻找所有可行的增广路径。封装：求从点 \(S\) 到点 \(T\) 的最大流。
template<typename T> struct Flow_ {const int n;const T inf = numeric_limits<T>::max();struct Edge {int to;T w;Edge(int to, T w) : to(to), w(w) {}};vector<Edge> ver;vector<vector<int>> h;vector<int> cur, d;Flow_(int n) : n(n + 1), h(n + 1) {}void add(int u, int v, T c) {h[u].push_back(ver.size());ver.emplace_back(v, c);h[v].push_back(ver.size());ver.emplace_back(u, 0);}bool bfs(int s, int t) {d.assign(n, -1);d[s] = 0;queue<int> q;q.push(s);while (!q.empty()) {auto x = q.front();q.pop();for (auto it : h[x]) {auto [y, w] = ver[it];if (w && d[y] == -1) {d[y] = d[x] + 1;if (y == t) return true;q.push(y);}}}return false;}T dfs(int u, int t, T f) {if (u == t) return f;auto r = f;for (int &i = cur[u]; i < h[u].size(); i++) {auto j = h[u][i];auto &[v, c] = ver[j];auto &[u, rc] = ver[j ^ 1];if (c && d[v] == d[u] + 1) {auto a = dfs(v, t, std::min(r, c));c -= a;rc += a;r -= a;if (!r) return f;}}return f - r;}T work(int s, int t) {T ans = 0;while (bfs(s, t)) {cur.assign(n, 0);ans += dfs(s, t, inf);}return ans;}
};
using Flow = Flow_<int>;
预流推进 HLPP
理论最坏复杂度为 \(\mathcal O(N^2\sqrt M)\) ，例题范围：\(N=1200,\ m=1.2\times 10^5\) 。
template <typename T> struct PushRelabel {const int inf = 0x3f3f3f3f;const T INF = 0x3f3f3f3f3f3f3f3f;struct Edge {int to, cap, flow, anti;Edge(int v = 0, int w = 0, int id = 0) : to(v), cap(w), flow(0), anti(id) {}};vector<vector<Edge>> e; vector<vector<int>> gap;vector<T> ex; // 超额流vector<bool> ingap;vector<int> h;int n, gobalcnt, maxH = 0;T maxflow = 0;PushRelabel(int n) : n(n), e(n + 1), ex(n + 1), gap(n + 1) {}void addedge(int u, int v, int w) {e[u].push_back({v, w, (int)e[v].size()});e[v].push_back({u, 0, (int)e[u].size() - 1});}void PushEdge(int u, Edge &edge) {int v = edge.to, d = min(ex[u], 1LL * edge.cap - edge.flow);ex[u] -= d;ex[v] += d;edge.flow += d;e[v][edge.anti].flow -= d;if (h[v] != inf && d > 0 && ex[v] == d && !ingap[v]) {++gobalcnt;gap[h[v]].push_back(v);ingap[v] = 1;}}void PushPoint(int u) {for (auto k = e[u].begin(); k != e[u].end(); k++) {if (h[k->to] + 1 == h[u] && k->cap > k->flow) {PushEdge(u, *k);if (!ex[u]) break;}}if (!ex[u]) return;if (gap[h[u]].empty()) {for (int i = h[u] + 1; i <= min(maxH, n); i++) {for (auto v : gap[i]) {ingap[v] = 0;}gap[i].clear();}}h[u] = inf;for (auto [to, cap, flow, anti] : e[u]) {if (cap > flow) {h[u] = min(h[u], h[to] + 1);}}if (h[u] >= n) return;maxH = max(maxH, h[u]);if (!ingap[u]) {gap[h[u]].push_back(u);ingap[u] = 1;}}void init(int t, bool f = 1) {ingap.assign(n + 1, 0);for (int i = 1; i <= maxH; i++) {gap[i].clear();}gobalcnt = 0, maxH = 0;queue<int> q;h.assign(n + 1, inf);h[t] = 0, q.push(t);while (q.size()) {int u = q.front();q.pop(), maxH = h[u];for (auto &[v, cap, flow, anti] : e[u]) {if (h[v] == inf && e[v][anti].cap > e[v][anti].flow) {h[v] = h[u] + 1;q.push(v);if (f) {gap[h[v]].push_back(v);ingap[v] = 1;}}}}}T work(int s, int t) {init(t, 0);if (h[s] == inf) return maxflow;h[s] = n;ex[s] = INF;ex[t] = -INF;for (auto k = e[s].begin(); k != e[s].end(); k++) {PushEdge(s, *k);}while (maxH > 0) {if (gap[maxH].empty()) {maxH--;continue;}int u = gap[maxH].back();gap[maxH].pop_back();ingap[u] = 0;PushPoint(u);if (gobalcnt >= 10 * n) {init(t);}}ex[s] -= INF;ex[t] += INF;return maxflow = ex[t];}
};