[题目小结] 网络流

东拼拼，西凑凑，不就又水出一篇博客吗？

例 1. \(\text{UVA12125 March of the Penguins}\)

首先可以想到在 \([1,n]\) 枚举汇点，检验最大流是否为企鹅总数。

每个点初始的企鹅数可以由 \(S\rightarrow i\) 的边表示，那跳出的企鹅呢？因为跳到哪个冰块是未知的，所以不妨将 \(i\) 拆成两个点 —— 在入点与出点之间连边权为跳出企鹅数的边。

例 2. \(\text{UVA11082 Matrix Decompressing}\)

这个建图真的好妙啊！假设每一行、列的数字和分别为 \(r_i,c_i\)，将行、列抽象成点，构造边 \(\langle S,i,r_i-m \rangle\)、\(\langle i,T,c_i-n \rangle\)。最后将任意行与列之间连接容量为 \(19\) 的边。

之所以将权值减一是因为网络流跑出的容量包含零，将区间变成 \([0,19]\)，再加一就可以复原。最后如果最大流满流就是有解的。

例 3. 圈地计划

不在同一部分是不好判断的，我们将网格图黑白染色，将黑格的商业区看作白格的工业区，这样就转化成了同一部分的问题！

对于两个相邻的点，连权值为 \(c_{i,j}+c_{i+1,j}\) 的 双向边，\(\text{sum}\) 只增加 \(c_{i,j}+c_{i+1,j}\)。这是因为这条双向边不可能同时删除所有方向。代码：\(\rm Link.\)

另外还有一种复杂度较高的做法：黑白染色之后，对每两个相邻的点建两个虚点 \(g_1,g_2\)，表示同时在左部/右部，分别连 \(\langle S,g_1 \rangle\)、\(\langle g_2,T\rangle\)，再以 \(\text{infty}\) 的权值连接虚点和相邻点。因为枚举了在哪一部，所以复杂度提高。

例 4. 「雅礼集训 2017 Day8」价

先说一下建图：

• 从源点向药 \(i\) 连接权值为 \(\text{infty}-w_i\) 的边。
• 从药向对应的药材连权值为 \(\text{infty}\) 的边。
• 从药材向汇点连权值为 \(\text{infty}\) 的边。

跑一遍最小割，答案就是最小割减去源点连出边的权值。

要想理解这个模型，首先得明确几个性质：

• 最小割不可能割去药与药材之间的边。因为一种药至少对应一种药材，所以割这条边一定不如割掉药材与汇点连边优。
• 割掉源点与药的连边相当于不选此药；割掉汇点与药材的连边相当于选择此药材。第一个比较好理解，对于第二个，考虑求最小割的过程：若药边未割（即选择药），那么药材必须割；若割，则药材可以不割。
• 一定只会割 \(n\) 条边。所有边都带 \(\text{infty}\)，多选一条边一定不优。
• 药和药材数相等。考虑上一条，即 —— 不选的药与选择的药材之和为 \(n\)，而不选的药与选择的药之和也为 \(n\)！所以结论得证。

最后考虑一下为什么定义 "割掉源点与药的连边相当于不选此药" 这样鬼畜的状态。如果我们将源点与药的连边权值改成 \(\text{infty}+w_i\)，即 "割掉源点与药的连边相当于选择此药"，此时药材边可以不割，但实际上我们需要必须不割！

总结：网络流建图时可以设计状态描述 "必须" 与 "可以"。

例 5. \(\text{UVA10735 Euler Circuit}\)

由于有向图存在欧拉回路当且仅当图连通且所有点的入度等于出度。考虑先将无向边定向，然后分配度数。

令 \(d'_i=\) 出度 \(-\) 入度，那么若 \(d'_i\) 为奇数则无解，否则令 \(d_i=d'_i/2\)。对于无向边 \(\langle u,v \rangle\)，若给它定向 \(u\rightarrow v\)，就在网络中连一条 \(u\rightarrow v\)，容量为 \(1\) 的边，表示 \(u\) 可以贡献一个 "度" 给 \(v\)。

对于 \(d_i>0\) 的点，从源点连容量为 \(d_i\) 的边；反之，向汇点连 \(-d_i\) 的边。这样最后检验从源点流出的边是否满流即可（检验汇点也可）。

跑一遍网络流后，当一条边的残余容量为零时，就说明反向。输出的时候记得将边反向遍历，就像这样：

void Print(int u) {
    while(!E[u].empty()) {
        int v=E[u].back(); E[u].pop_back();
        Print(v); printf(" %d",u);  
    }
}

例 6. \(\text{[JSOI 2009]}\) 游戏

首先一个比较经典的转化是按坐标之和的奇偶性将格点分成两部，这样 \(\text{Alice}\) 和 \(\text{Bob}\) 就只能分别走某一部。

可以证明，当 \(\text{Alice}\) 从一个 不一定 属于最大匹配的点出发，\(\text{Alice}\) 有必胜策略 —— 先假设这个点不属于某个最大匹配 \(G\)，此时 \(\text{Bob}\) 一定 只能 走到一个属于 \(G\) 的点，现在 \(\text{Alice}\) 可以选择走到与当前点匹配的点，下一步，\(\text{Bob}\) 可以走哪些点呢？

看似可以走不属于 \(G\) 的点，但事实上，如果存在这种点，我们就成功找到了一条增广路！这并不符合 \(G\) 是最大匹配的条件。于是 \(\text{Bob}\) 只能走属于 \(G\) 的点，\(\text{Alice}\) 沿用之前的策略，就可以达到必胜的效果。

于是问题转化为，如何求得不一定属于最大匹配的点。最 \(\text{naive}\) 的思路是删去一个点再求最大匹配，不过难道就没有更高效的做法吗？

事实上，先用 \(\text{Dinic}\) 求出一个最大匹配，从一个非匹配点出发，如果到达与自己 同部 的点，那么这些点都是非匹配点。这实际上是 "非匹配 - 匹配 - 非匹配 ..." 的过程，将匹配反向就可以使同部的点状态取反。

具体实现：

• 从源点出发沿 未满流 的边走，回到 \(S\) 部。
• 从汇点出发沿 满流 的边走，回到 \(T\) 部。

注意特判走到源/汇的情况。

例 7. \(\text{[SDOI 2016] }\)数字配对

考虑网络流。思考如何判断数字配对的条件 —— 朴素显然是 \(\mathcal O(n^2\sqrt V)\) 的，难以接受。

试图将质因数分解从二层循环抛到外面去：其实可以发现，配对条件满足当且仅当存在整除关系且质因数个数和相差为 \(1\)。这个问题就解决了。

如何连边？通过上文不难发现这是一张二分图，按质因数个数的奇偶性分类。于是要求最大化配对就变成了最大流。由于需要保证获得的价值总和不小于 \(0\)，我们优先选择费用更大的，也即 "最大费用最大流"。这个可以用 \(\text{spfa}\) 来解决。

例 8. \(\text{[CQOI 2014] }\)危桥

一点点题外话：呜呜呜我真 \(\rm tm\) 要哭了，根本想不到这题的转化，然而隔壁老王直接把这题切了，焯！

第一步转化是，从 \(a_1\) 到 \(a_2\) 再回来等价于从 \(a_1\) 到 \(a_2\) 走两次，所以可以流 \(a_n\) 条从 \(a_1\) 到 \(a_2\) 的流，把危桥的容量设定为 \(1\)（注意危桥双向容量均为 \(1\)）。

接下来最基本的思路是建立源汇 \(S,T\)，从 \(S\) 向 \(a_1,b_1\) 分别连容量为 \(a_n,b_n\) 的边，\(T\) 部分同理。然后跑一遍最大流查看是否满流。然而会出现两个问题：

• 可能存在 \(a_1\rightarrow b_2,b_1\rightarrow a_2\) 的流；
• 危桥可能正反各走一次。

解决方案是，先跑一遍最大流查看是否满流，再把 \(S\) 向 \(b_1\) 的连边改成向 \(b_2\) 连边，\(T\) 部分同理，跑一遍最大流查看是否满流，若还是满流才输出 Yes。这看上去没啥道理，所以接下来给出证明（你觉得我会严格证明吗？

假设第一次跑最大流，\(a_1\rightarrow b_2\) 的流量为 \(f\)，那么可以推出 \(a_1\rightarrow a_2\) 的流量为 \(a_n-f\)、\(b_1\rightarrow b_2\) 的流量为 \(b_n-f\) 两个结论，从而得出 \(b_1\rightarrow a_2\) 的流量为 \(f\).

而第二次跑最大流，\(a_1\rightarrow a_2,b_2\rightarrow b_1\) 的流量仍然分别为 \(a_n-f,b_n-f\). 对于 \(a_1\rightarrow a_2\)，这是因为图除了与 \(S,T\) 的连边外都没有变，而且这条路径没有使用 \(S\rightarrow b_1\) 或 \(S\rightarrow b_2\) 贡献的流量，所以这个转化对其并无影响；对于 \(b_2\rightarrow b_1\)，可以发现就是 \(b_1\rightarrow b_2\) 的路径反流，所以也无影响。于是又可以推出 \(a_1\rightarrow b_1,b_2\rightarrow a_2\) 的流量为 \(f\).

草，剩下的部分可能还得再想想……

对于第二个问题，利用反证法。假设从 \(a_1\) 到 \(a_2\) 的路径中有两条（同一条路径不需要证明了吧??）路径，路径 \(i\) 经过危桥 \(\langle u,v\rangle\)，另一条路径 \(j\) 又经过危桥 \(\langle v,u\rangle\)，那么为啥不把 \(i,j\) 在经过危桥之后的部分交换一下，这样就都不会经过危桥了；接下来考虑从 \(a_1\) 到 \(a_2\) 的路径经过危桥 \(\langle u,v\rangle\)，另一条从 \(b_1\) 到 \(b_2\) 的路径又经过危桥 \(\langle v,u\rangle\)，此时跑第二次最大流从 \(b_2\) 到 \(b_1\) 的路径就会经过危桥 \(\langle u,v\rangle\)，所以已经被判掉了。