题解：CF1666K Kingdom Partition

· · 题解

起因是 flama 大神讲课时有人提到了这个题。这个题有一个对最小割具有深刻启示作用的做法，我们后面再说，先来展示一下主播的做法。

神秘的做法

一个点有三个状态，这很不最小割，考虑如何刻画成两个集合。我一开始的想法是，把每个点拆成三个点 (u,0/1/2)，代表 [u\in A/B/C] 这个布尔变量，但随即发现连边的限制长成这样：若 (u,0)\in S，且 (u,1) 和 (u,2) 都属于 T，则有代价 2w。与运算也太难处理了，我们无法控制两个点都没割 T，于是倒闭了。

但是我们真的倒闭了吗？发现我们是会或运算的，所以想办法往上靠吧。注意到如果我们将原题的无向边，当成两条有向边来看待，即拆成两条「若 u\in A,v\in A，则消耗 w 代价」的边，那实际上两端点都为 A/B 与一端点为 C 消耗的代价就一样了！我们就不用把这两个东西分开看待了。再次修改状态，令 (u,0/1) 分别代表 [u\in A]\vee [u\in C]，以及 [u\in B]\vee [u\in C]。对于原图的边 (u,v,w)，我们分别连 \Big((u,0),(v,1),w\Big),\Big((u,1),(v,0),w\Big),\Big((v,0),(u,1),w\Big),\Big((v,1),(u,0),w\Big) 四条边即可，代表若 u 选 A/C，v 不选 B/C（即选 A）有 w 的代价；若 u 选 B/C，v 不选 A/C（即选 B）有 w 的代价；将 u,v 反过来同理。对于另一种限制 a\in A,b\in B，直接连 \Big(s,(a,0),\text{inf}\Big),\Big(s,(b,1),\text{inf}\Big),\Big((a,1),t,\text{inf}\Big),\Big((b,0),t,\text{inf}\Big) 即可，代表如果这么选你会万劫不复。

看起来很美好，但是会发现还有一个 case，即当 (u,0),(u,1) 属于同一个集合时怎么处理。如果此时 u\in C 是合理的，但如果出现 [u\in A]\wedge [u\in B] 的情况就不对了，我们的建模中并没有判掉这种情况。但当我们将这种情况代入上面的连边时，发现实际上这种点与 C 集合中的点的消耗是相同的，因此我们可以把这种矛盾的点当成 u\in C，并没有问题。构造方案的话，就从 s 开始，在残量网络上搜，每次只经过没被割的边即可。这样搜到的状态的布尔值就是一。对于点 u，若 (u,0/1) 中只有一个被搜到过就输出对应的那个集合，否则输出 C 即可。

下面展示更具有启发意义的做法。

不神秘的做法

最小割的另一种表达方式是，你有若干个布尔变量 x_1,x_2,\dots,x_n，还有若干限制 (u,v,w) 形如「若 x_u=1,x_v=0，则消耗 w 的代价」，要给这 n 个变量赋值并最小化总代价 \sum\limits_{(u,v,w)\in E}wx_u(1-x_v)。考虑将每个点只拆成两个状态 x_A,x_B，代表 [x\in A] 与 [x\in B] 两个变量，这样 [x\in C] 就可以表示成 1-x_A-x_B。根据上式，重新写一下本题的式子：

\sum\limits_{(u,v,w)\in E}2wx_{u,A}x_{v,A}+2wx_{u,B}x_{v,B}+wx_{u,A/B}(1-x_{v,A}-x_{v,B})+wx_{v,A/B}(1-x_{u,A}-x_{u,B})

这非常不像最小割，考虑通过移项让其变成最小割的形式。有：

\sum\limits_{(u,v,w)\in E}wx_{u,A}(1-x_{v,B})+wx_{u,B}(1-x_{v,A})+wx_{v,A}(1-x_{u,B})+wx_{v,B}(1-x_{u,A})

这很最小割。直接根据式子反推回建模即可。但会发现还有一个 case，即当 x_{u,A}=x_{v,A}=1 时如何处理。考虑这种点在式子中的贡献，将 A/B/C 三类点以及这种点作为边的另一端点带进上式，发现贡献分别为 (w,w,0,0)，这与 C 类点的贡献一模一样！因此我们不必再考虑这种点，并没有问题。

两种做法的建模是一样的，你可以看作第一种做法是在为第二种做法的 x_{u,A/B} 找「组合意义」。在遇到类似的 0/1 赋值题目时，可以考虑第二种做法用式子套上最小割。

submission：https://codeforces.com/contest/1666/submission/336108915