「2019 Multi-University Training Contest 2」Harmonious Army
题目链接：HDU 6598在一个军队里有 $n$ 名士兵。每名士兵需要分配一个任务：Mage 或 Warrior。这些士兵中有 $m$ 对士兵有良好的凝聚力。如果这两名士兵都参加 Warrior 任务，军队的效率会增加 $a$；如果这两名士兵都参加 Mage 任务，军队的效率会增加 $c$；否则军队的效率会增加 $b = \frac{a}{4} + \frac{c}{3}$（保证 $4 \mid a, 3 \mid c$）。你需要求出军队效率的最大值。本题有多组数据。数据范围：$1 \le n \le 500$，$0 \le m \le 10 ^ 4$，$1 \le a, b \le 4 \times 10 ^ 6$，$\sum n \le 5 \times 10 ^ 3$，$\sum m \le 5 \times 10 ^ 4$。Solution考虑「网络流」。我们对于点 $u, v$ 建立如下网络图（我才不会告诉你们图片是从官方题解搬来的）：设三种贡献分别为 $A, B, C$，通过最小割的实际意义，我们建立方程：$$ \begin{cases} a + b = A + B \\ c + d = C + B \\ a + d + e = A + C \\ b + c + e = A + C \end{cases} $$解得一组解为：$$ \begin{cases} a = b = \frac{A + B}{2} \\ c = d = \frac{C + B}{2} \\ e = \frac{A + C - 2B}{2} \end{cases} $$直接跑最小割即可。时间复杂度：$\mathcal O(n ^ {2} m)$。Code#include <cstdio> #include <algorithm> #include <queue> const int N = 5e2 + 5, M = 1e4 + 5; const int INF = 0x7f7f7f7f; int n, m, vs[N], vt[N]; template <class Tp, int N, int M, bool opt> struct Network { static const int INF = 0x7f7f7f7f; int n, tot = 1, lnk[N], cur[N], ter[M], nxt[M], dis[N]; Tp cap[M], flow[M]; void clear() { std::fill(lnk + 1, lnk + n + 1, 0); n = 0, tot = 1; } void addEdge(int u, int v, Tp w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot; cap[tot] = w, flow[tot] = 0; } void addArc(int u, int v, Tp w) { addEdge(u, v, w), addEdge(v, u, 0); } #if opt Tp dif[N]; void addArc(int u, int v, Tp l, Tp r) { dif[u] -= l, dif[v] += l, addArc(u, v, r - l); } #endif bool bfs(int s, int t) { std::queue<int> q; std::fill(dis + 1, dis + n + 1, INF); std::copy(lnk + 1, lnk + n + 1, cur + 1); dis[s] = 0, q.push(s); for (; !q.empty(); ) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] > flow[i] && dis[v] == INF) { dis[v] = dis[u] + 1, q.push(v); } } } return dis[t] < INF; } Tp dfs(int u, int t, Tp f) { if (u == t) return f; Tp ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] > flow[i] && dis[v] == dis[u] + 1) { Tp x = dfs(v, t, std::min(f, cap[i] - flow[i])); flow[i] += x, flow[i ^ 1] -= x, f -= x, ans += x; if (f == 0) break; } } return ans; } Tp dinic(int s, int t) { Tp ans = 0; for (; bfs(s, t); ) { for (Tp x; (x = dfs(s, t, INF)); ans += x); } return ans; } }; Network<long long, N, 4 * N + 4 * M, false> F; int main() { for (; scanf("%d%d", &n, &m) == 2; ) { F.clear(); int s = n + 1, t = F.n = n + 2; std::fill(vs + 1, vs + n + 1, 0); std::fill(vt + 1, vt + n + 1, 0); long long ans = 0; for (int i = 1, u, v, a, b, c; i <= m; i++) { scanf("%d%d%d%d%d", &u, &v, &a, &b, &c); vs[u] += a + b, vs[v] += a + b; vt[u] += b + c, vt[v] += b + c; F.addArc(u, v, a + c - b - b); F.addArc(v, u, a + c - b - b); ans += a + b + c; } for (int i = 1; i <= n; i++) { F.addArc(s, i, vs[i]); F.addArc(i, t, vt[i]); } printf("%lld\n", ans - F.dinic(s, t) / 2); } return 0; }
题目链接：LOJ 2226宅男 JYY 非常喜欢玩 RPG 游戏，比如仙剑，轩辕剑等等。不过 JYY 喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在 JYY 想花费最少的时间看完所有的支线剧情。JYY 现在所玩的 RPG 游戏中，一共有 $n$ 个剧情点，由 $1$ 到 $n$ 编号，第 $i$ 个剧情点可以根据 JYY 的不同的选择，而经过不同的支线剧情，前往 $K_i$ 种不同的新的剧情点。当然 $K_i$ 如果为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。JYY 观看一个支线剧情需要一定的时间。JYY 一开始处在 $1$ 号剧情点，也就是游戏的开始。显然任何一个剧情点都是从 $1$ 号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。由于 JYY 过度使用修改器，导致游戏的「存档」和「读档」功能损坏了，所以 JYY 要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到 $1$ 号剧情点。JYY 可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情很是痛苦，JYY 希望花费最少的时间，看完所有不同的支线剧情。数据范围：$1 \le n \le 300$，$0 \le K_i \le 50$，$\sum_{i = 1} ^ n K_i \le 5000$。Solution刚看到题目可能会想到最小链覆盖，但是发现每条链必须从起点出发，并且边有权值，我们可以尝试往网络流的方向思考。每条边至少经过 $1$ 次可以转化为这条边的流量下界为 $1$，上界为 $\infty$，费用为花费时间。直接套用有源汇有上下界费用流求解即可。时间复杂度：$\mathcal O(n\sum K_i f)$。Code#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 3e2 + 5, M = 2e4 + 5; const int INF = 0x7f7f7f7f; int n, m, deg[N], dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M]; bool vis[N]; void add(int u, int v, int w, int c) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c; } void addEdge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); } bool spfa(int s, int t) { memset(dis, 0x7f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0, vis[s] = true; while (!q.empty()) { int u = q.front(); q.pop(), vis[u] = false; for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; if (!vis[v]) q.push(v), vis[v] = true; } } } return dis[t] < INF; } int dfs(int u, int t, int flow) { if (u == t) return flow; vis[u] = true; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && !vis[v] && dis[v] == dis[u] + cost[i]) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) break; } } vis[u] = false; return ans; } std::pair<int, int> dinic(int s, int t) { int maxFlow = 0, minCost = 0; while (spfa(s, t)) { int x; while ((x = dfs(s, t, INF))) maxFlow += x, minCost += x * dis[t]; } return std::make_pair(maxFlow, minCost); } int main() { scanf("%d", &n); int s = 1, t = n + 1, ans = 0; for (int u = 1; u <= n; u++) { int k; scanf("%d", &k); for (int j = 1; j <= k; j++) { int v, c; scanf("%d%d", &v, &c); deg[u]--, deg[v]++, ans += c; addEdge(u, v, INF, c); } addEdge(u, t, INF, 0); } int ss = 0, tt = n + 2; for (int i = 1; i <= n; i++) { if (deg[i] > 0) addEdge(ss, i, deg[i], 0); if (deg[i] < 0) addEdge(i, tt, -deg[i], 0); } addEdge(t, s, INF, 0); printf("%d\n", ans + dinic(ss, tt).second); return 0; }
[scode type="green"]所谓上下界网络流，就是在网络图中给每条边指定一个流量下界和上界。这类网络流问题有很多模型，需要根据不同性质进行转化。[/scode]网络流系列文章最大流最小割费用流上下界网络流概述本文中，我们用 $(u, v, l, r)$ 来表示边 $(u, v)$ 的容量的下界为 $l$、上界为 $r$；用 $s', t'$ 表示虚源点和虚汇点；用 $s, t$ 表示源点和汇点。我们将上下界网络流问题分成若干类，下文将具体展开讲述。无源汇可行流思路首先我们需要增加虚源点和虚汇点，然后考虑如何建图。对于边 $(u, v, l, r)$，流量 $l$ 是必须流过的，流量 $r - l$ 是自由流量。换言之，如果我们强制从 $u$ 流出 $l$ 的流量，强制向 $v$ 流入 $l$ 的流量，那么就可以转化为容量为 $r - l$ 的一般网络流问题了。这个问题看似比较难处理，那么我们先考虑一个判定性问题：这种网络图是否有可行流？通过上述分析可以将这个问题转化为：是否可以从 $u$ 流出 $l$ 的流量，向 $v$ 流入 $l$ 的流量？现在这个问题已经比较容易了，我们将边 $(u, v, l, r)$ 拆成如下 $3$ 条边：边 $(s', v)​$，容量为 $l​$，也就是强制向 $v​$ 流入 $l​$ 的流量。边 $(u, t')$，容量为 $l$，也就是强制从 $u$ 流出 $l$ 的流量。边 $(u, v)$，容量为 $r - l$，也就是自由流量。下文将前 $2$ 条边称为附加边。接下来在这种图上跑最大流。判断是否可行的方法为：附加边是否满流；换言之就是最大流是否为所有边的下界容量之和。如果有解，我们只需要将每条边的流量加上下界容量就是一组可行流了。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 4e5 + 5; const int INF = 0x7f7f7f7f; int n, m, low[M], deg[N], dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w; } void addEdge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } bool bfs(int s, int t) { memset(dis, -1, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] < 0) { q.push(v), dis[v] = dis[u] + 1; } } } return dis[t] >= 0; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] == dis[u] + 1) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) return ans; } } dis[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v, l, r; scanf("%d%d%d%d", &u, &v, &l, &r); deg[u] -= l, deg[v] += l, low[i] = l; addEdge(u, v, r - l); } int ss = 0, tt = n + 1, sum = 0; for (int i = 1; i <= n; i++) { if (deg[i] > 0) addEdge(ss, i, deg[i]), sum += deg[i]; if (deg[i] < 0) addEdge(i, tt, -deg[i]); } if (dinic(ss, tt) != sum) { puts("No"); } else { puts("Yes"); for (int i = 1; i <= m; i++) { printf("%d\n", cap[(i << 1) | 1] + low[i]); } } return 0; }有源汇可行流思路我们发现，此时源点和汇点不满足流量平衡，那么我们连一条边 $(t, s, 0, \infty)$ 使得源点流向汇点的流量重新流回去。经过转化，有源汇可行流也转化为了无源汇可行流问题。我们只需要和无源汇问题一样拆边建模即可。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 4e5 + 5; const int INF = 0x7f7f7f7f; int n, m, s, t, low[M], deg[N], dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w; } void addEdge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } bool bfs(int s, int t) { memset(dis, -1, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] < 0) { q.push(v), dis[v] = dis[u] + 1; } } } return dis[t] >= 0; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] == dis[u] + 1) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) return ans; } } dis[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, l, r; scanf("%d%d%d%d", &u, &v, &l, &r); deg[u] -= l, deg[v] += l, low[i] = l; addEdge(u, v, r - l); } addEdge(t, s, INF); int ss = 0, tt = n + 1, sum = 0; for (int i = 1; i <= n; i++) { if (deg[i] > 0) addEdge(ss, i, deg[i]), sum += deg[i]; if (deg[i] < 0) addEdge(i, tt, -deg[i]); } if (dinic(ss, tt) != sum) { puts("No"); } else { puts("Yes"); for (int i = 1; i <= m; i++) { printf("%d\n", cap[(i << 1) | 1] + low[i]); } } return 0; }有源汇最大流思路首先我们按照有源汇可行流的方法进行建模，接下来的讨论均在存在可行流的情况下进行。在网络图上先得到从 $s'$ 到 $t'$ 的可行流，之后在残量网络上跑一遍从 $s$ 到 $t$ 的最大流，此时得到的最大流就是答案。这个算法的正确性证明如下：由于我们在原图上跑过最大流，在附加边满流的情况下，我们已经把流量下界这个条件消去了。这样一来，在新图中的 $s$ 到 $t$ 的任何一种可行流都是原图的可行流，这样跑出来的最大流就是原图的最大流。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 4e5 + 5; const int INF = 0x7f7f7f7f; int n, m, s, t, deg[N], dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w; } void addEdge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } bool bfs(int s, int t) { memset(dis, -1, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] < 0) { q.push(v), dis[v] = dis[u] + 1; } } } return dis[t] >= 0; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] == dis[u] + 1) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) return ans; } } dis[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, l, r; scanf("%d%d%d%d", &u, &v, &l, &r); deg[u] -= l, deg[v] += l; addEdge(u, v, r - l); } int ss = 0, tt = n + 1, sum = 0; for (int i = 1; i <= n; i++) { if (deg[i] > 0) addEdge(ss, i, deg[i]), sum += deg[i]; if (deg[i] < 0) addEdge(i, tt, -deg[i]); } addEdge(t, s, INF); printf("%d\n", dinic(ss, tt) == sum ? dinic(s, t) : -1); return 0; }有源汇最小流思路建图方式和最大流一样，但是不要建立 $(t, s, 0, \infty)$ 这条边。在这种图上我们得到 $s'$ 到 $t'$ 的最大流；之后连上 $(t, s, 0, \infty)$ 这条边得到新图上的最大流；此时的最大流就是原图的最小流。考虑证明这个过程的正确性。之前讲过，边 $(t, s)$ 上的流量就是原图的流量；现在我们要最小化这个值，就要尽可能多消耗掉可能要经过这条边的流量。第一次跑最大流的时候没有连上这条边，因此 $s$ 到 $t$ 的流量已经尽可能往别的地方流了，就可以最小化这个值了。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 4e5 + 5; const int INF = 0x7f7f7f7f; int n, m, s, t, deg[N], dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w; } void addEdge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } bool bfs(int s, int t) { memset(dis, -1, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] < 0) { q.push(v), dis[v] = dis[u] + 1; } } } return dis[t] >= 0; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] == dis[u] + 1) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) return ans; } } dis[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, l, r; scanf("%d%d%d%d", &u, &v, &l, &r); deg[u] -= l, deg[v] += l; addEdge(u, v, r - l); } int ss = 0, tt = n + 1, sum = 0; for (int i = 1; i <= n; i++) { if (deg[i] > 0) addEdge(ss, i, deg[i]), sum += deg[i]; if (deg[i] < 0) addEdge(i, tt, -deg[i]); } int ans = dinic(ss, tt); addEdge(t, s, INF); ans += dinic(ss, tt); printf("%d\n", ans == sum ? cap[tot] : -1); return 0; }有源汇费用流思路首先需要注意的是：上下界网络流中的最小费用流没有最大流前提，而是可行流的最小费用！这个过程和有源汇可行流很相似。对于一条边 $(u, v, l, r, c)$，我们将其拆成 $3$ 条边：边 $(s', v)$，容量为 $l$，费用为 $0$。边 $(u, t')$，容量为 $l$，费用为 $0$。边 $(u, v)$，容量为 $r - l$，费用为 $c$。按照套路，我们还要连边 $(t, s, 0, \infty, 0)$，当然费用也是 $0$。我们求出 $s'$ 到 $t'$ 的最小费用最大流，最终的费用还要加上每条边的下界乘上其费用。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 4e5 + 5; const int INF = 0x7f7f7f7f; int n, m, s, t, low[N], deg[N], dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M]; bool vis[N]; void add(int u, int v, int w, int c) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c; } void addEdge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); } bool spfa(int s, int t) { memset(dis, 0x7f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0, vis[s] = true; while (!q.empty()) { int u = q.front(); q.pop(), vis[u] = false; for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; if (!vis[v]) q.push(v), vis[v] = true; } } } return dis[t] < INF; } int dfs(int u, int t, int flow) { if (u == t) return flow; vis[u] = true; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && !vis[v] && dis[v] == dis[u] + cost[i]) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) break; } } vis[u] = false; return ans; } std::pair<int, int> dinic(int s, int t) { int maxFlow = 0, minCost = 0; while (spfa(s, t)) { int x; while ((x = dfs(s, t, INF))) maxFlow += x, minCost += x * dis[t]; } return std::make_pair(maxFlow, minCost); } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, l, r, c; scanf("%d%d%d%d%d", &u, &v, &l, &r, &c); deg[u] -= l, deg[v] += l, low[i] = l; addEdge(u, v, r - l, c); } int ss = 0, tt = n + 1, sum = 0; for (int i = 1; i <= n; i++) { if (deg[i] > 0) addEdge(ss, i, deg[i], 0), sum += deg[i]; if (deg[i] < 0) addEdge(i, tt, -deg[i], 0); } addEdge(t, s, INF, 0); std::pair<int, int> ans = dinic(ss, tt); if (ans.first != sum) { puts("-1"); } else { for (int i = 1; i <= m; i++) { ans.second += low[i] * cost[i << 1]; } printf("%d %d\n", ans.first, ans.second); } return 0; }习题 「LOJ 115」无源汇有上下界可行流 「LOJ 116」有源汇有上下界最大流 「LOJ 117」有源汇有上下界最小流 网络流 24 题 「LOJ 6000」搭配飞行员 「LOJ 6001」太空飞行计划 「LOJ 6002」最小路径覆盖 「LOJ 6003」魔术球 「LOJ 6004」圆桌聚餐 「LOJ 6005」最长递增子序列 「LOJ 6006」试题库 「LOJ 6007」方格取数 「LOJ 6008」餐巾计划 「LOJ 6009」软件补丁 「LOJ 6010」数字梯形 「LOJ 6011」运输问题 「LOJ 6012」分配问题 「LOJ 6013」负载平衡 「LOJ 6014」最长 k 可重区间集 「LOJ 6015」星际转移 「LOJ 6121」孤岛营救问题 「LOJ 6122」航空路线问题 「LOJ 6223」汽车加油行驶问题 「LOJ 6224」深海机器人问题 「LOJ 6225」火星探险问题 「LOJ 6226」骑士共存问题 「LOJ 6227」最长 k 可重线段集问题
题目链接：UOJ 336曾经有一款流行的游戏，叫做Infinity Loop，先来简单的介绍一下这个游戏：游戏在一个 $n \times m$ 的网格状棋盘上进行，其中有些小方格中会有水管，水管可能在方格某些方向的边界的中点有接口，所有水管的粗细都相同，所以如果两个相邻方格的公共边界的中点都有接头，那么可以看作这两个接头互相连接。水管有以下 $15$ 种形状：游戏开始时，棋盘中水管可能存在漏水的地方。形式化地：如果存在某个接头，没有和其它接头相连接，那么它就是一个漏水的地方。玩家可以进行一种操作：选定一个含有非直线型水管的方格，将其中的水管绕方格中心顺时针或逆时针旋转 $90$ 度。直线型水管是指左图里中间一行的两种水管。现给出一个初始局面，请问最少进行多少次操作可以使棋盘上不存在漏水的地方。如果无法达成目标，输出 $-1$。数据范围：$1 \le n \times m \le 2000$。Solution借鉴一下 Tiger0132 博客中的一句话：判断网络流的一个办法：网格图 / 棋盘 / 有规律的图案有一些与暴力算法无关的奇怪性质这道题：是棋盘；直管不能翻转。鉴定完毕。于是我们考虑如何建模。由于有旋转操作，于是我们把每个格子拆成 $4$ 个点，分别代表上下左右四个方向。又观察到是否漏水只和相邻两个格子有关，于是我们对棋盘进行黑白染色。黑点连向源点，白点连向汇点（注意这里的点是水管有接口的方向上的所有点），容量为 $1$，费用为 $0$。我们把合法的接头数量看做是流量，将旋转次数看做是费用。如果最大流量等于要求的接头数量，那么最小费用就是最少的交换次数。对于每个格子​，我们用 ​$\text{U}, \text{R}, \text{D}, \text{L}$ 表示其拆点后的上、右、下、左四个点。对于格子 $(i, j)$，我们将 $\text{U}_{i, j}, \text{R}_{i, j}, \text{D}_{i, j}, \text{L}_{i, j}$ 分别和 $\text{D}_{i - 1, j}, \text{L}_{i, j + 1}, \text{U}_{i + 1, j}, \text{R}_{i, j - 1}$ 连一条容量为 $1$，费用为 $0$ 的边（注意连边方向是从源点向汇点）。对于所有的水管形态，我们将它们分为本质不同的几种：直管、十字直管不能旋转，因此不需要考虑旋转导致的连边；十字旋转不会产生任何影响，因此也不需要额外连边。单叉、直角、三叉考虑一次旋转造成的影响：获得一个新的方向上的接口，同时失去一个方向上的接口。那么我们从被删除的方向上的点向获得的方向上的点连一条容量为 $1$，费用为旋转次数的边。正确性考虑证明这样连边的正确性。每个点向源汇点连边的容量均为 $1$，意味着只能旋转一次、并且代表一个接口数量。一个部分的点只会和另一个部分的唯一一个点匹配，正确性得证。建好图之后直接跑最小费用最大流即可。时间复杂度：$\mathcal O(n ^ 3 m ^ 3)$。Code#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define U k + 0 #define R k + 1 #define D k + 2 #define L k + 3 #define E(x, y, c) addEdge(x, y, 1, c, opt) const int N = 8e3 + 5, M = 1.5e5 + 5; const int INF = 0x3f3f3f3f; int n, m, maxFlow, minCost, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N]; bool vis[N]; void add(int u, int v, int w, int c) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c; } void addEdge(int u, int v, int w, int c, bool rev) { if (rev) std::swap(u, v); add(u, v, w, c), add(v, u, 0, -c); } bool spfa(int s, int t) { memset(dis, 0x3f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0, vis[s] = true; while (!q.empty()) { int u = q.front(); q.pop(), vis[u] = false; for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; if (!vis[v]) q.push(v), vis[v] = true; } } } return dis[t] != INF; } int dfs(int u, int t, int flow) { if (u == t) return flow; vis[u] = true; int ans = 0; for (int &i = cur[u]; i && ans < flow; i = nxt[i]) { int v = ter[i]; if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) { int x = dfs(v, t, std::min(cap[i], flow - ans)); if (x) { cap[i] -= x, cap[i ^ 1] += x; ans += x, minCost += x * cost[i]; } } } vis[u] = false; return ans; } void mcmf(int s, int t) { maxFlow = minCost = 0; while (spfa(s, t)) { int x; while ((x = dfs(s, t, INF))) maxFlow += x; } } int id(int i, int j) { return ((i - 1) * m + j - 1) * 4 + 1; } int main() { scanf("%d%d", &n, &m); int s = 0, t = 4 * n * m + 1, cnt = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int x, k = id(i, j), opt = (i + j) & 1; scanf("%d", &x); if (i > 1) E(U, id(i - 1, j) + 2, 0); if (j > 1) E(L, id(i, j - 1) + 1, 0); if (x & 1) E(opt ? t : s, U, 0), cnt++; if (x & 2) E(opt ? t : s, R, 0), cnt++; if (x & 4) E(opt ? t : s, D, 0), cnt++; if (x & 8) E(opt ? t : s, L, 0), cnt++; switch(x) { case 1: E(U, L, 1), E(U, D, 2), E(U, R, 1); break; case 2: E(R, D, 1), E(R, L, 2), E(R, U, 1); break; case 4: E(D, L, 1), E(D, U, 2), E(D, R, 1); break; case 8: E(L, U, 1), E(L, R, 2), E(L, D, 1); break; case 3: E(U, D, 1), E(R, L, 1); break; case 6: E(R, L, 1), E(D, U, 1); break; case 12: E(D, U, 1), E(L, R, 1); break; case 9: E(L, R, 1), E(U, D, 1); break; case 7: E(U, L, 1), E(R, L, 2), E(D, L, 1); break; case 14: E(R, U, 1), E(D, U, 2), E(L, U, 1); break; case 13: E(D, R, 1), E(L, R, 2), E(U, R, 1); break; case 11: E(L, D, 1), E(U, D, 2), E(R, D, 1); break; } } } mcmf(s, t); printf("%d\n", maxFlow << 1 == cnt ? minCost : -1); return 0; }
「Codeforces 280D」K-Maximum Subsequence Sum
题目链接：Codeforces 280D你有一个长度为 $n$ 的序列 $a_i$，接下来进行 $m$ 次操作，操作分为如下 $2$ 种：0 i val：将第 $i$ 个数 $a_i$ 修改为 $val$。1 l r k：你需要在序列 $a_l, a_{l + 1}, \cdots, a_r$ 中找出至多 $k$ 个不相交的子序列，使得他们的和最大。形式化地，你需要找出至多 $k$ 对 $(x_1, y_1), (x_2, y_2), \cdots, (x_t, y_t)$（其中 $l\le x_1\le y_1<x_2\le y_2<\cdots<x_t \le y_t\le r$，$0\le t\le k$），使得 $(a_{x_1} + a_{x_1 + 1} + \cdots + a_{y_1}) + (a_{x_2} + a_{x_ 2 + 1} + \cdots + a_{y_2})+\cdots + (a_{x_t} + a_{x_t + 1} + \cdots + a_{y_t})$ 的值最大。特别地，你可以选择 $0$ 个子序列，这时和式等于 $0$。数据范围：$1 \le n, m\le 10 ^ 5$，$\vert a_i, val \vert \le 500$，$1\le k\le 20$，求 $k$ 个子序列和的操作不超过 $10^4$ 个。Solution我们很容易建立起费用流的模型。源点像每个点连流量为 $1$、费用为 $0$ 的边。每个点向下一个点连流量 $1$，费用为 $a_i$ 的边。每个点向汇点连流量为 $1$、费用为 $0$ 的边。可以发现多流一个单位的流量就会多出一个区间。那么问题就变成使用不超过 $k$ 个单位的流量，能够得到的最大费用。但是直接上费用流肯定 $\text{TLE}$，但是注意到每次増广的贡献是一段区间，我们考虑用线段树维护来模拟费用流。我们把増广的过程转化为线段树能处理的问题：每次増广相当于询问整个区间的最大子段和。每次更新反向弧的费用相当于将区间取反。増广 $k$ 次相当于在线段树上进行上述过程 $k$ 次。这样一来我们就可以直接在线段树上操作了！最后考虑一下代码实现问题！由于我们要实现区间最大子段和及其范围、区间取反，因此需要维护的不止左右端点最大值、区间最大答案……对于每个最大值，还需要记录最小值，这样才能实现区间取反的问题。为了使代码难度降低，我们可以定义一个 $\text{struct}$ 记录每个值的 $l,r,val$ 等信息，重载运算符来合并区间。时间复杂度：$\mathcal O(mk\log n)$ 且带有大常数。Code#include <cstdio> #include <algorithm> #define lson p << 1 #define rson p << 1 | 1 const int N = 1e5 + 5; int n, m, A[N]; struct Data { int l, r, val; Data(int _l = 0, int _r = 0, int _val = 0) { l = _l, r = _r, val = _val; } Data operator+(const Data &b) const { return Data(l, b.r, val + b.val); } bool operator<(const Data &b) const { return val < b.val; } }; struct Node { int rev; Data sum, lmx, lmn, rmx, rmn, smx, smn; Node() { rev = 0; sum = lmx = lmn = rmx = rmn = smx = smn = Data(); } void init(int pos, int val) { rev = 0; sum = lmx = lmn = rmx = rmn = smx = smn = Data(pos, pos, val); } void reverse() { rev ^= 1; std::swap(lmx, lmn); std::swap(rmx, rmn); std::swap(smx, smn); sum.val *= -1; lmx.val *= -1, lmn.val *= -1; rmx.val *= -1, rmn.val *= -1; smx.val *= -1, smn.val *= -1; } }; struct Segment { Node a[N << 2]; Node merge(Node x, Node y) { Node ans; ans.sum = x.sum + y.sum; ans.lmx = std::max(x.lmx, x.sum + y.lmx); ans.lmn = std::min(x.lmn, x.sum + y.lmn); ans.rmx = std::max(y.rmx, x.rmx + y.sum); ans.rmn = std::min(y.rmn, x.rmn + y.sum); ans.smx = std::max(x.rmx + y.lmx, std::max(x.smx, y.smx)); ans.smn = std::min(x.rmn + y.lmn, std::min(x.smn, y.smn)); return ans; } void pushdown(int p) { if (a[p].rev) { a[lson].reverse(); a[rson].reverse(); a[p].rev = 0; } } void build(int p, int l, int r) { if (l == r) { a[p].init(l, A[l]); return; } int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r); a[p] = merge(a[lson], a[rson]); } void modify(int p, int l, int r, int x, int v) { if (l == r) { a[p].init(l, v); return; } pushdown(p); int mid = (l + r) >> 1; if (x <= mid) { modify(lson, l, mid, x, v); } else { modify(rson, mid + 1, r, x, v); } a[p] = merge(a[lson], a[rson]); } void reverse(int p, int l, int r, int x, int y) { if (l == x && y == r) { a[p].reverse(); return; } pushdown(p); int mid = (l + r) >> 1; if (y <= mid) { reverse(lson, l, mid, x, y); } else if(x > mid) { reverse(rson, mid + 1, r, x, y); } else { reverse(lson, l, mid, x, mid); reverse(rson, mid + 1, r, mid + 1, y); } a[p] = merge(a[lson], a[rson]); } Node query(int p, int l, int r, int x, int y) { if (l == x && y == r) { return a[p]; } pushdown(p); int mid = (l + r) >> 1; if (y <= mid) { return query(lson, l, mid, x, y); } else if(x > mid) { return query(rson, mid + 1, r, x, y); } else { return merge(query(lson, l, mid, x, mid), query(rson, mid + 1, r, mid + 1, y)); } } } seg; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &A[i]); } seg.build(1, 1, n); scanf("%d", &m); for (int i = 1; i <= m; i++) { int opt; scanf("%d", &opt); if (!opt) { int x, v; scanf("%d%d", &x, &v); seg.modify(1, 1, n, x, v); } else { int l, r, k; scanf("%d%d%d", &l, &r, &k); int ans = 0, tp = 0; Data st[25]; for (int j = 1; j <= k; j++) { Node now = seg.query(1, 1, n, l, r); if (now.smx.val < 0) { break; } ans += now.smx.val; st[++tp] = now.smx; seg.reverse(1, 1, n, now.smx.l, now.smx.r); } for (int j = 1; j <= tp; j++) { seg.reverse(1, 1, n, st[j].l, st[j].r); } printf("%d\n", ans); } } return 0; }
[scode type="green"]最小费用最大流，指在保证最大流量的同时最小费用。[/scode]网络流系列文章最大流最小割费用流上下界网络流概念费用我们定义一条边的费用 $w(u,v)$ 表示边 $(u,v)$ 上单位流量的费用。也就是说，当边 $(u,v)$ 的流量为 $f(u,v)$ 时，需要花费 $f(u,v)\times w(u,v)$ 的费用。最小费用最大流网络流图中，花费最小的最大流被称为最小费用最大流，这也是接下来我们要研究的对象。求解我们可以在 $\text{Dinic}​$ 算法的基础上进行改进，把 $\text{BFS}​$ 求分层图改为用 $\text{SPFA}​$（由于有负权边，所以不能直接用 $\text{Dijkstra}​$）来求一条单位费用之和最小的路径，也就是把 $w(u,v)​$ 当做边权然后在残量网络上求最短路，当然在 $\text{DFS}​$ 中也要略作修改。这样就可以求得网络流图的最小费用最大流了。如何建反向边？对于一条边 $(u,v,w,c)$（其中 $w$ 和 $c$ 分别为容量和费用），我们建立正向边 $(u,v,w,c)$ 和反向边 $(v,u,0,-c)$（其中 $-c$ 是使得从反向边经过时退回原来的费用）。优化：如果你是“关于 $\text{SPFA}$，它死了”言论的追随者，那么你可以使用 $\text{Primal-Dual}$ 原始对偶算法将 $\text{SPFA}$ 改成 $\text{Dijkstra}$！时间复杂度：可以证明上界为 $\mathcal O(nmf)$，其中 $f$ 表示流量。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 2e5 + 5; const int INF = 0x7f7f7f7f; int n, m, s, t, dis[N]; int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M]; bool vis[N]; void add(int u, int v, int w, int c) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c; } void addEdge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); } bool spfa(int s, int t) { memset(dis, 0x7f, sizeof(dis)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dis[s] = 0, vis[s] = true; while (!q.empty()) { int u = q.front(); q.pop(), vis[u] = false; for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; if (!vis[v]) q.push(v), vis[v] = true; } } } return dis[t] < INF; } int dfs(int u, int t, int flow) { if (u == t) return flow; vis[u] = true; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] && !vis[v] && dis[v] == dis[u] + cost[i]) { int x = dfs(v, t, std::min(cap[i], flow)); if (!x) continue; cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x; if (!flow) break; } } vis[u] = false; return ans; } std::pair<int, int> dinic(int s, int t) { int maxFlow = 0, minCost = 0; while (spfa(s, t)) { int x; while ((x = dfs(s, t, INF))) maxFlow += x, minCost += x * dis[t]; } return std::make_pair(maxFlow, minCost); } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c); addEdge(u, v, w, c); } std::pair<int, int> ans = dinic(s, t); printf("%d %d\n", ans.first, ans.second); return 0; }习题「LOJ 102」最小费用流网络流 24 题「LOJ 6000」搭配飞行员「LOJ 6001」太空飞行计划「LOJ 6002」最小路径覆盖「LOJ 6003」魔术球「LOJ 6004」圆桌聚餐「LOJ 6005」最长递增子序列「LOJ 6006」试题库「LOJ 6007」方格取数「LOJ 6008」餐巾计划「LOJ 6009」软件补丁「LOJ 6010」数字梯形「LOJ 6011」运输问题「LOJ 6012」分配问题「LOJ 6013」负载平衡「LOJ 6014」最长 k 可重区间集「LOJ 6015」星际转移「LOJ 6121」孤岛营救问题「LOJ 6122」航空路线问题「LOJ 6223」汽车加油行驶问题「LOJ 6224」深海机器人问题「LOJ 6225」火星探险问题「LOJ 6226」骑士共存问题「LOJ 6227」最长 k 可重线段集问题
题目链接：BZOJ 1001现在小朋友们最喜欢的"喜羊羊与灰太狼"，话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：左上角点为 $(1,1)$，右下角点为 $(n,m)$（上图中 $n=3, m=4​$）。有以下三种类型的道路：$(x,y)\longleftrightarrow(x+1,y)$$(x,y)\longleftrightarrow(x,y+1)$$(x,y)\longleftrightarrow(x+1,y+1)$道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的。左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里，现在它们要跑到右下角 $(n,m)$ 的窝中去，狼王开始伏击这些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为 $k$，狼王需要安排同样数量的 $k$ 只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。数据范围：$1\le n, m\le 1000$。Solution很显然是一个裸的最小割，对 $(1,1)$ 到 $(n,m)$ 依次编号，然后按照题意建边跑最短路即可 QAQ吐槽：终于做出了 BZOJ 的 1001（大雾当然由于这题的图是一张平面图，所以我们也可以建出对偶图，直接跑最短路，得到的就是原图的最小割。时间复杂度：$\mathcal O((nm)^3)$。Code#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e6 + 5, M = 6e6 + 5; const int INF = 0x3f3f3f3f; int n, m, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N]; int id(int x, int y) { return (x - 1) * m + y; } void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w; } void addEdge(int u, int v, int w) { add(u, v, w), add(v, u, w); } int bfs(int s, int t) { memset(dep, 0, sizeof(dep)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (val[i] && !dep[v]) { q.push(v), dep[v] = dep[u] + 1; } } } return dep[t]; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i && ans < flow; i = nxt[i]) { int v = ter[i]; if (val[i] && dep[v] == dep[u] + 1) { int x = dfs(v, t, std::min(val[i], flow - ans)); if (x) { val[i] -= x, val[i ^ 1] += x, ans += x; } } } if (ans < flow) dep[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j < m; j++) { int x; scanf("%d", &x); addEdge(id(i, j), id(i, j + 1), x); } } for (int i = 1; i < n; i++) { for (int j = 1; j <= m; j++) { int x; scanf("%d", &x); addEdge(id(i, j), id(i + 1, j), x); } } for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { int x; scanf("%d", &x); addEdge(id(i, j), id(i + 1, j + 1), x); } } printf("%d\n", dinic(id(1, 1), id(n, m))); return 0; }
[scode type="green"]最小割，指割去一些边使得源点和汇点不连通的最小花费，有最大流最小割定理。[/scode]网络流系列文章最大流最小割费用流上下界网络流概念割对于一个网络流图 $G=(V,E)$，其割的定义为一种点的划分方式：将所有的点划分为 $S$ 和 $T=V-S$ 两个集合，其中源点 $s\in S$，汇点 $t\in T$。割的容量我们的定义割 $(S,T)$ 的容量 $c(S,T)$ 表示所有从 $S$ 到 $T$ 的边的容量之和，即 $c(S,T)=\sum_{u\in S,v\in T}c(u,v)$。当然我们也可以用 $c(s,t)$ 表示 $c(S,T)$。最小割最小割就是求得一个割 $(S,T)$ 使得割的容量 $c(S,T)$ 最小。证明最大流最小割定理定理：$f(s,t)_{\max}=c(s,t)_{\min}$对于任意一个可行流 $f(s,t)$ 的割 $(S,T)$，我们可以得到：$$ f(s,t)=S\ \text{出边的总流量}-S\ \text{入边的总流量}\le S\ \text{出边的总流量}=c(s,t) $$如果我们求出了最大流 $f$，那么残余网络中一定不存在 $s$ 到 $t$ 的増广路经，也就是 $S$ 的出边一定是满流，$S$ 的入边一定是零流，于是有：$$ f(s,t)=S\ \text{出边的总流量}-S\ \text{入边的总流量}=S\ \text{出边的总流量}=c(s,t) $$结合前面的不等式，我们可以知道此时 $f$ 已经达到最大。代码最小割通过最大流最小割定理，我们可以直接得到如下代码：#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e4 + 5, M = 2e5 + 5; const int INF = 0x3f3f3f3f; int n, m, s, t, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w; } void addedge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } int bfs(int s, int t) { memset(dep, 0, sizeof(dep)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (val[i] && !dep[v]) { q.push(v), dep[v] = dep[u] + 1; } } } return dep[t]; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int &i = cur[u]; i && ans < flow; i = nxt[i]) { int v = ter[i]; if (val[i] && dep[v] == dep[u] + 1) { int x = dfs(v, t, std::min(val[i], flow - ans)); if (x) { val[i] -= x, val[i ^ 1] += x, ans += x; } } } if (ans < flow) dep[u] = -1; return ans; } int dinic(int s, int t) { int ans = 0; while (bfs(s, t)) { int x; while ((x = dfs(s, t, INF))) ans += x; } return ans; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); } printf("%d\n", dinic(s, t)); return 0; }方案我们可以通过从源点 $s$ 开始 $\text{DFS}$，每次走残量大于 $0$ 的边，找到所有 $S$ 点集内的点。void dfs(int u) { vis[u] = 1; for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (!vis[v] && val[i]) dfs(v); } }割边数量只需要将每条边的容量变为 $1$，然后重新跑 $\text{Dinic}$ 即可。问题模型有 $n$ 个物品和两个集合 $A,B$，如果将一个物品放入 $A$ 集合会花费 $a_i$，放入 $B$ 集合会花费 $b_i$；还有若干个形如 $u_i,v_i,w_i$ 限制条件，表示如果 $u_i$ 和 $v_i$ 同时不在一个集合会花费 $w_i$。每个物品必须且只能属于一个集合，求最小的代价。这是一个经典的二者选其一的最小割题目。我们对于每个集合设置源点 $s$ 和汇点 $t$，第 $i$ 个点由 $s$ 连一条容量为 $a_i$ 的边、向 $t$ 连一条容量为 $b_i$ 的边。对于限制条件 $u,v,w$，我们在 $u,v$ 之间连容量为 $w$ 的双向边。注意到当源点和汇点不相连时，代表这些点都选择了其中一个集合。如果将连向 $s$ 或 $t$ 的边割开，表示不放在 $A$ 或 $B$ 集合，如果把物品之间的边割开，表示这两个物品不放在同一个集合。最小割就是最小花费。习题「USACO 4.4」Pollutant Control「USACO 5.4」Telecowmunication「Luogu 1361」小 M 的作物「SHOI 2007」善意的投票网络流 24 题「LOJ 6000」搭配飞行员「LOJ 6001」太空飞行计划「LOJ 6002」最小路径覆盖「LOJ 6003」魔术球「LOJ 6004」圆桌聚餐「LOJ 6005」最长递增子序列「LOJ 6006」试题库「LOJ 6007」方格取数「LOJ 6008」餐巾计划「LOJ 6009」软件补丁「LOJ 6010」数字梯形「LOJ 6011」运输问题「LOJ 6012」分配问题「LOJ 6013」负载平衡「LOJ 6014」最长 k 可重区间集「LOJ 6015」星际转移「LOJ 6121」孤岛营救问题「LOJ 6122」航空路线问题「LOJ 6223」汽车加油行驶问题「LOJ 6224」深海机器人问题「LOJ 6225」火星探险问题「LOJ 6226」骑士共存问题「LOJ 6227」最长 k 可重线段集问题
[scode type="green"]在二分图最大匹配问题中，每个点最多只能和一条匹配边相关联。但是二分图多重匹配中，每个点可以多次匹配但是有匹配上限。[/scode]例题Description学校运动会即将开始，运动会有 $m$ 个项目，第 $i$ 个项目每个班必须派出 $p_i$ 名学生参加。班级里有 $n$ 名学生，第 $i$ 名学生最多参加 $a_i$ 个项目，并且他给出了他擅长的 $b_i​$ 个项目的编号。求是否有一个合适的安排满足条件。数据范围：$1\le n,m\le 100$。Solution我们把 $n$ 名学生和 $m$ 个项目看作是二分图的 $A,B$ 两部。那么每个学生向他擅长的项目连边。这就是二分图匹配的一般思想。由于有 $a_i$ 和 $p_i$ 的限制，我们要求 $A$ 部的点关联的边不能超过 $a_i$ 个，那么我们需要一个方法来限制这个量在 $[0,a_i]$ 之间。这样一来，有没有感觉特别想网络流中的容量？于是我们可以对二分图进行扩展，建立源点 $s$ 和汇点 $t$，在 $s$ 和 $A$ 部的第 $i$ 个点之间连一条容量为 $a_i$ 的边，在 $A$ 部和 $B$ 部之间相连的边的容量为 $1$，从 $B$ 部的第 $i$ 个点向 $t$ 连一条容量为 $p_i$ 的边。这个连边方式的正确性显然。我们对这张图跑最大流，然后分析一下各个边的含义：边 $(s,A_i)$ 表示学生 $A_i$ 参加的项目数量。边 $(A_i,B_j)$ 表示 $A_i$ 是否参加了 $B_j$ 项目。边 $(B_i,t)$ 表示项目 $B_i$ 的参加人数。所以是否有合适方案，我们只要判断是否所有的边 $(B_i,t)$ 都满流即可！时间复杂度：$\mathcal O((n+m)\cdot(nm)^2)$。Code#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 205, M = 5e4 + 5; const int INF = 0x3f3f3f3f; int n, m, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N]; int id(int p, int x) { return p == 1 ? x : n + x; } void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w; } void addedge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } int bfs(int s, int t) { memset(dep, 0, sizeof(dep)); memcpy(cur, lnk, sizeof(lnk)); std::queue<int> q; q.push(s), dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (val[i] && !dep[v]) { q.push(v), dep[v] = dep[u] + 1; } } } return dep[t]; } int dfs(int u, int t, int flow) { if (u == t) return flow; int ans = 0; for (int i = cur[u]; i && ans < flow; i = nxt[i]) { int v = ter[i]; if (val[i] && dep[v] == dep[u] + 1) { int x = dfs(v, t, std::min(val[i], flow - ans)); if (x) { val[i] -= x, val[i ^ 1] += x, ans += x; } } } if (ans < flow) dep[u] = -1; return ans; } void dinic(int s, int t) { while (bfs(s, t)) while (dfs(s, t, INF)); } int main() { scanf("%d%d", &n, &m); int s = 0, t = n + m + 1; for (int i = 1; i <= m; i++) { int x; scanf("%d", &x); addedge(id(2, i), t, x); } for (int i = 1; i <= n; i++) { int x, y; scanf("%d%d", &x, &y); addedge(s, id(1, i), x); for (int k = 1; k <= y; k++) { int j; scanf("%d", &j); addedge(id(1, i), id(2, j), 1); } } dinic(s, t); bool flg = 1; for (int i = lnk[t]; i; i = nxt[i]) { flg &= !val[i ^ 1]; } puts(flg ? "Yes" : "No"); return 0; }习题「hihoCoder 1393」网络流三·二分图多重匹配「POJ 2289」Jamie's Contact Groups「POJ 3189」Steady Cow Assignment「POJ 1698」Alice's Chance「HDU 3605」Escape
[scode type="green"]最大流，指一张网络图中的最大流量。[/scode]网络流系列文章最大流最小割费用流上下界网络流概念网络流网络流是指给定一个有向图，其中有两个特殊的点：源点 $s$（Source）和汇点 $t$（Sink）；每条边都有一个指定的流量上限，下文均称之为容量（Capacity），即经过这条边的流量不能超过容量，这样的图被称为网络流图。同时，除了源点和汇点外，所有点的入流和出流都相等，源点只有流出的流，汇点只有流入的流，网络流就是从 $s$ 到 $t$ 的一个可行流。可行流定义 $c(u,v)$ 表示边 $(u,v)$ 的容量，$f(u,v)$ 表示边 $(u,v)$ 的流量。如果满足 $0\le f(u,v)\le c(u,v)$，则称 $f(u,v)$ 为边 $(u,v)$ 上的流量。如果有一组流量满足：源点 $s$ 的流出量等于整个网络的流量，汇点 $t$ 的流入量等于整个网络的流量，除了任意一个不是 $s$ 或 $t$ 的点的总流入量等于总流出量。那么整个网络中的流量被称为一个可行流。最大流在所有可行流中，最大流指其中流量最大的一个流的流量。定义我们定义（部分定义在上文有涉及）：源点 $s$：只有流出量的点。汇点 $t$：只有流入量的点。容量 $c$：$c(u,v)$ 表示边 $(u,v)$ 上的容量。流量 $f$：$f(u,v)$ 表示边 $(u,v)$ 上的流量。残量 $w$：$w(u,v)$ 表示边 $(u,v)$ 上的残量（显然有 $w(u,v)=c(u,v)-f(u,v)$）。性质容量限制对于任何一条边，都有 $0\le f(u,v)\le c(u,v)$。斜对称性对于任何一条边，都有 $f(u,v)=-f(v,u)$。即从 $u$ 到 $v$ 的流量一定等于从 $v$ 到 $u$ 的流量的相反数。流守恒性对于任何一个点 $u$，如果满足 $u\neq s$ 并且 $u\neq t$，那么一定有 $\sum f(u,v)=0$，即 $u$ 到相邻节点的流量之和为 $0$。因为 $u$ 本身不会制造和消耗流量。求解増广路网络流的所有算法都基于増广路的思想，接下来首先介绍一下増广路思想。找到一条从 $s$ 到 $t$ 的路径，使得路径上的每一条边都有 $w(u,v)>0$ 即残量大于 $0$。注意：这里是严格 $>$ 而不是 $\ge$，这意味着这条边还可以分配流量。这条路径就被叫做増广路。找到这条路径上最小的 $w(u,v)$，记为 $flow$。将这条路径上的每一条边的 $w(u,v)$ 减去 $flow$。重复上述过程，直到找不到増广路为止。注意：其实上述方法并不是正确的，但这是一个非常重要的分析过程，因此请读者仔细阅读！我们可以根据这个过程在下面这张图中模拟一遍。如果我们把每条边的的信息用残量 / 容量表示出来，可以得到下图：假设我们第一次找到的増广路为 $1-2-3-4$，那么我们把这条路径上的边的 $w(u,v)$ 减去 $\min\{f(u,v)\}$ 即 $1$，得到下图：然后呢……我们发现已经没有増广路了，此时算出来的“最大流”为 $1$！但是我们可以手动计算一下，这张图的最大流其实是 $2$！这个最大流的路径为 $1-2-4$（流量为 $1$）和 $1-3-4$（流量为 $1$）。因此，我们可以发现这样的过程是错误的。原因就是増广路在一定意义上是有顺序的，说白了就是没有给它反悔的机会。所以我们要引入反向边的概念。反向边改进通过上文的分析我们已经知道，当我们在寻找増广路的时候，找到的并不一定是最优解。如果我们对正向边的 $w(u,v)$ 减去 $flow$ 的同时，将对应的反向边的 $w(v,u)$ 加上 $flow$，我们就相当于可以反悔从这条边流过。那么我们可以建立反向边，初始时每条边的 $w(u,v)=c(u,v)$，它的反向边的 $w(v,u)=0$（显然反向边不能有流量，因此残量为 $0$）。接下来再看一下上面那个例子，我们只用 $w(u,v)$ 来表示每条边（包括反向边）的信息：接下来开始寻找増广路，假如还是 $1-2-3-4$ 这条路径。我们需要把 $w(1,2)$，$w(2,3)$，$w(3,4)$ 减少 $1$，同时把反向边的 $w(2,1)$，$w(3,2)$，$w(4,3)$ 增加 $1$。那么可以得到下图：继续从 $s$ 开始寻找増广路（不需要考虑边的类型），显然可以发现路径 $1-3-2-4$，其中 $flow=1​$。更新边的信息，得到下图：此时我们发现没有増广路了，为了直观观察这个网络，我们去掉反向边，显然我们求出的最大流为 $2$！正确性当我们第二次増广边 $(2,3)$ 走这条反向边 $(3,2)$ 时，把 $(2,3)$ 和 $(3,2)$ 的流量抵消了，相当于把 $(2,3)$ 这条正向边的流量给退了回去使得可以不走 $(2,3)$ 这条边。如果反向边 $(v,u)$ 的流量不能完全抵消正向边 $(u,v)$，那么意味着从 $u$ 开始还可以流一部分流量到 $v$，这样也是允许的。小技巧如何快速找到反向边？如果使用邻接表存图，那么可以对边从 $2$ 开始编号，那么下标为 $i$ 的边的反向边就是 $i\ \text{XOR}\ 1$。思路总结最初这个网络的流量为 $0$，称为零流。找到一条从 $s$ 到 $t$ 的路径，使得路径上的每一条边都有 $w(u,v)>0$ 即残量大于 $0$。注意：这里是严格 $>$ 而不是 $\ge$，这意味着这条边还可以分配流量。这条路径就被叫做増广路。找到这条路径上最小的 $w(u,v)$，记为 $flow$。将这条路径上的每一条边的 $w(u,v)$ 减去 $flow$，同时将反向边 $(v,u)$ 的 $w(v,u)$ 加上 $flow$。重复上述过程，直到找不到増广路为止，此时的流量就是最大流。这个算法基于増广路定理：网络达到最大流当且仅当残留网络中没有増广路。然而我不会证明 QAQ算法求最大流有若干种算法，此处介绍其中的两种：$\text{Edmonds-Karp}$ 和 $\text{Dinic}$。Edmonds-Karp实现过程简称 $\text{EK}$ 算法，每次用 $\text{BFS}$ 求出一条増广路径，通过记录每个点的前驱和这条边的编号来记录下这条路径。可以说是对増广路思路的完全模拟。但是 $\text{EK}$ 在某些情况下会被卡得很慢。假如有下面这张图：其中 $w(u,v)=1$，其余正向边的 $w(u,v)=100$。如果第一次増广路的策略不恰当，找到了 $1-2-3-4$，那么 $w(2,3)=0$，$w(3,2)=1$。接下来又会找到増广路经 $1-3-2-4$，然后又是 $1-2-3-4$……然后显然最大流路径就是 $1-2-4$（流量为 $100$）和 $1-3-4$（流量为 $100$），但是如果策略不当，就会这样不断这样増广下去，导致复杂度会爆炸！复杂度$\text{EK}$ 算法的时间复杂度为 $\mathcal O(nm^2)$。我们可以证明最多需要 $\mathcal O(nm)$ 次増广可以达到最大流，每次増广的复杂度为 $\mathcal O(m)$。绝大多数情况下这个复杂度都跑不满。代码#include <cstdio> #include <cstring> #include <algorithm> #include <queue> const int N = 1e5 + 5, M = 2e5 + 5; const int INF = 0x7f7f7f7f; int n, m, s, t; int tot = 1, lnk[N], ter[M], nxt[M], cap[M], pre[N], idx[N]; bool vis[N]; void add(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w; } void addEdge(int u, int v, int w) { add(u, v, w), add(v, u, 0); } bool bfs(int s, int t) { memset(pre, 0, sizeof(pre)); memset(vis, 0, sizeof(vis)); std::queue<int> q; q.push(s), vis[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (!vis[v] && cap[i]) { pre[v] = u, idx[v] = i, q.push(v), vis[v] = 1; if (v == t) return 1; } } } return 0; } int EK(int s, int t) { int ans = 0; while (bfs(s, t)) { int mn = INF; for (int i = t; i != s; i = pre[i]) { mn = std::min(mn, cap[idx[i]]); } for (int i = t; i != s; i = pre[i]) { int x = idx[i]; cap[x] -= mn, cap[x ^ 1] += mn; } ans += mn; } return ans; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addEdge(u, v, w); } printf("%d\n", EK(s, t)); return 0; }Dinic实现过程我们发现 $\text{EK}$ 在某些情况下会很低效，我们有另一个算法 $\text{Dinic}$。它引入了分层图的概念，具体的方法如下：为了避免走重复的路径，从 $s$ 开始 $\text{BFS}$ 对图分层，将整个图分为若干层，其中 $s$ 是第 $1$ 层。如果一条边的残量为 $0$，那么忽略这条无法増广的边。如果 $t$ 的层数不为 $0$，那么意味着存在増广路径。如果存在増广路，那么从 $s$ 开始进行 $\text{DFS}$ 寻找从源点到汇点的増广路，注意此处増广必须要按照图的层次来遍历。每次下传当前流量 $flow$（初始流量认为是无穷大）。设 $dep_i$ 表示 $i$ 的层次，$ans$ 代表当前从 $u$ 可以流的流量，对于当前点 $u$ 相连的点 $v$，如果 $dep_v=dep_u+1$ 并且 $w(u,v)>0$，那么可以増广。此时下传的 $flow$ 应为 $\min(w(u,v),flow-ans)$，其中 $flow-ans$ 代表从 $u$ 还可以流的流量（已经有 $ans$ 的流量从 $v'$ 流出去了）。当 $ans\ge flow$ 时意味着没有可以流的流量了，应该退出増广。如果该 $\text{DFS}$ 找到的可以増广的流量为 $0$，表示增广失败，跳过这条边。否则将 $w(u,v)$ 减去増广的流量，将 $w(v,u)$ 和 $ans$ 加上相同的值。小剪枝：如果遍历完所有的 $v$ 后 $ans < flow$，意味着已经从 $u$ 流出了所有可以増广的流量，即 $u$ 已经满流了，此时需要将 $dep_u$ 设为 $-1$，防止再次从这个点増广。优化$\text{Dinic}$ 算法还有一个优化，被称为当前弧优化，即每次 $\text{DFS}$ 増广时不是从 $u$ 出发的第 $1$ 个点开始，而是用一个 $cur$ 数组记录点 $u$ 増广到了哪条边，从这条边开始増广，以此来进一步加速。复杂度$\text{Dinic}$ 算法的时间复杂度为 $\mathcal O(n^2m)$。我们可以证明最多需要建立 $\mathcal O(n)$ 个层次图，每次建立层次图的复杂度为 $\mathcal O(m)$。接下来分析 $\text{DFS}$ 的复杂度，每次最多増广 $\mathcal O(m)$ 次，每次修改流量的复杂度为 $\mathcal O(n)$，所以 $\text{DFS}$ 的复杂度为 $\mathcal O(nm)$。再加上 $\mathcal O(n)$ 个层次图，总复杂度为 $\mathcal O(n^2m)$。绝大多数情况下这个复杂度都跑不满。对于 $\text{Dinic}$ 算法的复杂度，有如下 $3$ 种情况：一般的网络图：$\mathcal O(n^2m)$单位容量的图：$\mathcal O(\min(\sqrt m,n^{\frac{2}{3}})\cdot m)$二分图：$\mathcal O(m\sqrt n)$代码void addEdge(int u, int v, int w) { ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w; } void addArc(int u, int v, int w) { addEdge(u, v, w), addEdge(v, u, 0); } bool bfs(int s, int t) { std::queue<int> q; std::fill(dis + s, dis + t + 1, -1); std::copy(lnk + s, lnk + t + 1, cur + s); dis[s] = 0, q.push(s); for (; !q.empty(); ) { int u = q.front(); q.pop(); for (int i = lnk[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] > flow[i] && dis[v] < 0) { dis[v] = dis[u] + 1, q.push(v); } } } return dis[t] >= 0; } int dfs(int u, int t, int f) { if (u == t) return f; int ans = 0; for (int &i = cur[u]; i; i = nxt[i]) { int v = ter[i]; if (cap[i] > flow[i] && dis[v] == dis[u] + 1) { int x = dfs(v, t, std::min(f, cap[i] - flow[i])); flow[i] += x, flow[i ^ 1] -= x, f -= x, ans += x; if (f == 0) break; } } return ans; } int dinic(int s, int t) { int ans = 0; for (; bfs(s, t); ) { for(int x; (x = dfs(s, t, INF)); ans += x); } return ans; }习题「LOJ 101」最大流「LOJ 127」最大流 加强版网络流 24 题「LOJ 6000」搭配飞行员「LOJ 6001」太空飞行计划「LOJ 6002」最小路径覆盖「LOJ 6003」魔术球「LOJ 6004」圆桌聚餐「LOJ 6005」最长递增子序列「LOJ 6006」试题库「LOJ 6007」方格取数「LOJ 6008」餐巾计划「LOJ 6009」软件补丁「LOJ 6010」数字梯形「LOJ 6011」运输问题「LOJ 6012」分配问题「LOJ 6013」负载平衡「LOJ 6014」最长 k 可重区间集「LOJ 6015」星际转移「LOJ 6121」孤岛营救问题「LOJ 6122」航空路线问题「LOJ 6223」汽车加油行驶问题「LOJ 6224」深海机器人问题「LOJ 6225」火星探险问题「LOJ 6226」骑士共存问题「LOJ 6227」最长 k 可重线段集问题