网络流建模学习笔记

一、二者取一式问题

二者取一式问题可以这样描述：将若干元素 $e_{1}, e_{2}, \dots, 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$ 作为汇点，那么这个网络的一个割就是一种划分方法。如果没有组合的话，我们很容易就能建立这样的模型：

v2-8ca41bb30358f5b4d95addf974e497c7_1440w

当我们去割它时，与 $A$ 连通的点代表放到 $A$ 集合中，与 $B$ 连通的点代表放到 $B$ 集合中。当这个割是最小割时，剩下的边的容量和是最大的，故设最小割为 cut，边权总和为 sum，则所求最大分值为 sum-cut。

现在我们考虑组合：假设 $C_{1} = {e_{1}, e_{2}}$ 且对应的额外分值为 $a_{1}^{'}$ 和 $b_{1}^{'}$ 。

我们从 $A$ 点伸出一条容量为 $a_{1}^{'}$ 的边通向虚点 $X$ ：

v2-7d33e345ace0c6873f633477c30ad9ba_1440w

现在我们的需求是：只有当 $1$ 、 $2$ 点都被归入 $A$ 所在点集时， $X$ 才与 $A$ 连通。

反过来想，当 $1$ 被归入 $B$ 所在点集时，要让 $A \to X$ 被割掉。很自然地想到，让 $X$ 连向 $1$ ，这样当 $1$ 被归入 $B$ 所在点集时， $A \to X \to 1$ 必然会断，否则 $A$ 就与 $B$ 连通了。但如何确保割掉的是 $A \to X$ 而不是 $X \to 1$ 呢？只要令 $X \to 1$ 的容量为 $I N F$ 即可，无穷大的边不会被割掉。 $2$ 号点同理。

v2-4f7c46fa4a92f473e8465d2a985c16d9_1440w

对于 $B$ 号点，道理是一样的：

v2-3f06c22d87598fc1b5c1774376d303c3_1440w

好了，这就是我们需要的模型。这时我们求最小割 cut，并记非无穷边权和为 sum，那么跟刚刚一样，sum-cut 就是所求分数。

自己的话

其实换一个角度来考虑，把原图看作最大权闭合子图的建模，初始时的每个节点看作 “选 $B$ 而不选 $A$ ” 的收益，选择某个节点就是将其改为划在 $A$ 内：

在 $B$ 内的组合初始时就是满足的，所以向汇点连边表示可能的负贡献（修改之后变成不满足了），所以要选某个节点，就一定要选与之相连的 $B$ 组合节点，表示不满足了，需要撤回收益
而在 $A$ 内的组合原来并不满足，向源点连边表示可能的正收益，向组合内成员连边表示如果你要获取这一份收益，你需要把这些成员全部划到 $A$ 内
由于初始时的收益相当于 $\sum b_{i} + \sum b_{i}^{'}$ ，而我们的闭合子图权值 $\sum a_{i} + \sum a_{i}^{'} - min C u t$ 的意义相当于价值的变化量，所以最后的总收益就相当于 $\sum b_{i} + \sum b_{i}^{'} + \sum a_{i} + \sum a_{i}^{'} - min C u t$ ，也就是总收益减去最小割