订阅更新(RSS/Atom): 最大流三倍经验： Luogu-P1402 酒店之王 / Luogu-P2891 [USACO07OPEN] Dining G 一眼丁真建图：S->练习册->书->答案->T 然而是错的。很明显，书有可能被多次匹配，与题意不符。正确的建图：S->练习册->书（拆点）->答案->T 为什么中间层的书要拆点呢？因为一本书不能被重复选用。我们的目的是保证一本书流出的流量只能是 $1$。所以我们把每个代表书的点拆成两个点，左边的点和练习册连边，右边的点和答案连边；左右对应点之间也要连一条容量为 $1$ 的边。定理：最小路径覆盖数=$|G|$-二分图最大匹配数首先我们假设现在原图内每个点都是一条路径，此时最少路径数为 $n$。考虑合并路径，当且仅当两条路径首尾相连的时候可以合并。将点 $x$ 拆成出点 $x$ 和入点 $x+n$，当我们连接 $u, v$ 时，转化为连接 $u, v+n$。将 $S$ 与所有 $u$ 连边，将所有 $u+n$ 与 $T$ 连边。所有边的容量都为 $1$。在一开始每个点都是一条独立的路径，每次合并将两条路径合并为一条路径，那么最终路径即为点数减去最大匹配数，这样求得的路径覆盖即为最小路径覆盖。对于输出路径，用 to 记录下一个节点，tag 标记该节点前面是否还有点。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 ll dfs(int u, int t, ll flow) { if (u == t) return flow; ll ans = 0; vis[u] = 1; for (int &i = cur[u]; ~i; i = e[i].nxt) { // i 用引用：当前弧优化 int v = e[i].to; if (!vis[v] && dep[v] == dep[u] + 1 && e[i].cap > e[i].flow) { ll d = dfs(v, t, min(flow - ans, e[i].cap - e[i].flow)); if (!d) continue; ans += d; e[i].flow += d; e[i ^ 1].flow -= d; to[u] = v; if (u != S) { tag[v - n] = 1; } if (ans == flow) break; // 剪枝，残余流量用尽，停止增广 } } vis[u] = 0; return ans; } ll Dinic(int s, int t) { ll ret = 0; while (bfs(s, t)) { memcpy(cur, fir, sizeof cur); ret += dfs(s, t, INF); } for (int i = 1; i <= n; i++) { if (tag[i] == 0) { cout << i << " "; int x = i; while (to[x] && to[x] != t) { cout << to[x] - n << " "; x = to[x] - n; } cout << "\n"; } } return ret; } int main() { ios::sync_with_stdio(false); memset(fir, -1, sizeof fir); cin >> n >> m; S = 2 * n + 1, T = S + 1; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; addEdge(x, y + n, 1); } for (int i = 1; i <= n; i++) { addEdge(S, i, 1); addEdge(i + n, T, 1); } int t = Dinic(S, T); cout << n - t << endl; return 0; } 方格取数问题对矩阵进行黑白染色，那么比如选了一个黑格，那么与它相邻的白格不能选。可以计算不选的方格，其余的都选。容易想到最小割。那么建图就很容易了。对于每个点 $(i,j)$，数值为 $a_{i,j}$，如果是白色点，那么从源点向它连一条容量 $a_{i,j}$ 的边；否则就从这个点向汇点连一条容量 $a_{i,j}$ 的边。这样我们就把不选的点转化成了割掉的边。为了保证相邻点直接的边不会被割掉，我们从每个白点向与其相邻的黑点连容量为 $INF$ 的边（他们之间的边只从白连到黑，避免重复计算）。答案为全局和减去最小割。原点向所有狼连容量 $INF$ 的边，所有羊向汇点连容量 $INF$ 的边，所有点向四周连容量为 $1$ 的边。最小割即为答案，因为狼和羊之间的边都被割掉了。二者取其一模型。考虑点集 ${u, v, w}$ 对集合 $A$ 的贡献，加入其中一者被割进 $B$，那这个点集就没有贡献，即点集与 $A$ 的连边要割掉。用一个虚点 $x$ 从 $S$ 连一条边代表贡献，如果其中一个点被割进了集合 $B$，那这条代表贡献的边也要割掉，而 $x$ 到 $u, v, w$ 的边不能断开。所以 $(S, x)$ 的容量为 $c$，$(x, u), (x, v), (x, w)$ 的容量都是 $INF$（保证不被断开）。答案为总收益减去最小割。两倍经验：Luogu-P3410 拍照最大权值闭合图模型。如果没有租机器，那这道题就是纯最大权值闭合图模型。图中对于工作和它所需的机器之间边的容量为 $INF$，所以这条边不可能被割，意义即为选择这个工作就必须购买这个机器。那么租用就可以将这条边的容量改为 $b_{ij}$，可以用 $b_{ij}$ 割掉这条边，表示选择这个工作后，可以花费 $b_{ij}$ 的代价代替购买机器。

网络流题集

剩余内容已隐藏查看完整文章以阅读更多

剩余内容已隐藏
查看完整文章以阅读更多