差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:lgwza:最小割 [2020/08/15 17:53]
lgwza 创建
+++ 2020-2021:teams:legal_string:lgwza:最小割 [2020/08/15 17:54] (当前版本)
lgwza [方案]
@@ 行 101: / 行 101: @@
 </code>
 </hidden>
+==== 方案 ====
+我们可以通过从源点 $s$ 开始 $\text{DFS}$，每次走残量大于 $0$ 的边，找到所有 $S$ 点集内的点。
+<code cpp>
+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);
+  }
+}
+</code>
+==== 割边数量 ====
+只需要将每条边的容量变为 $1$，然后重新跑 $\text{Dinic}$ 即可。
+===== 问题模型——二者取一式问题 =====
+二者取一式问题可以这样描述：将若干元素 $e_1,e_2,e_3,\cdots,e_n$ 划分到两个集合 $A,B$ 中。对于元素 $e_i$，它被划分到 $A$ 或 $B$ 中分别能获得一个 $a_{e_i}$ 或 $b_{e_i}$ 的分值。除此之外，还给出若干个组合 $C_i\subseteq A$，当组合中的元素被同时划分到 $A$ 或 $B$ 时，可以获得额外的分值 $a_i'$ 或 $b_i'$。求最大的分值。
+这个问题可以被转化为网络流中的 **最小割**问题。如果我们把 $A$ 作为源点，$B$ 作为汇点，那么这个网络的一个 **割** 就是一种划分方法。如果没有组合的话，我们很容易就能建出这样的模型：
+{{https://picb.zhimg.com/80/v2-8ca41bb30358f5b4d95addf974e497c7_720w.jpg| img}}
+当我们去割它时，与 $A$ 连通的点代表放到 $A$ 集合中，与 $B$ 连通的点代表放到 $B$ 集合中。当这个割是最小割时，剩下的边的容量和是最大的，故设最小割为 ''%%cut%%''，边权总和为 ''%%sum%%''，则所求最大分值为 ''%%sum-cut%%''。
+现在我们考虑组合。假设 $C_1=\{e_1,e_2\}$，且对应的额外分值为 $a_1'$ 和 $b_1'$。我们从 $A$ 点伸出一条容量为 $a_1'$ 的边通向虚点 $X$：
+{{https://pic4.zhimg.com/80/v2-7d33e345ace0c6873f633477c30ad9ba_720w.jpg| img}}
+现在我们的需求是：只有当 1、2 点都被归入 $A$ 所在点集时，$X$ 才与 $A$ 连通。
+反过来想，当 1 被归入 $B$ 所在点集时，要让 $A\rightarrow X$ 被割掉。很自然地想到，让 $X$ 连向 1，这样当 1 被归入 $B$ 所在点集时，$A\rightarrow X\rightarrow 1$ 必然会断，否则 $A$ 就与 $B$ 连通了。但如何确保割掉的是 $A\rightarrow X$ 而不是 $X\rightarrow 1$ 呢？只要令 $X\rightarrow 1$ 的容量为 INF 即可，无穷大边不会被割掉。2 号点同理。
+{{https://pic2.zhimg.com/80/v2-4f7c46fa4a92f473e8465d2a985c16d9_720w.jpg| img}}
+对于 $B$ 号点，道理是一样的：
+{{https://pic2.zhimg.com/80/v2-3f06c22d87598fc1b5c1774376d303c3_720w.jpg| img}}
+好了，这就是我们需要的模型。这时我们求最小割 ''%%cut%%''，并记非无穷边权和为 ''%%sum%%''，那么跟刚刚一样，''%%sum-cut%%'' 就是所求分数。
+===== 习题 =====
+[[https://www.luogu.com.cn/problem/P1344|「USACO 4.4」Pollutant Control]]
+[[https://www.luogu.com.cn/problem/P1345|「USACO 5.4」Telecowmunication]]
+[[https://www.luogu.com.cn/problem/P1361|「Luogu 1361」小 M 的作物]]
+[[https://www.luogu.com.cn/problem/P2057|「SHOI 2007」善意的投票]]
+===== 参考链接 =====
+[[https://oi-wiki.org/graph/flow/min-cut/|OI Wiki]]
+[[https://zhuanlan.zhihu.com/p/123308502|算法学习笔记(29): 二者取一式问题]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具