题解：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$。根据上式，重新写一下本题的式子：

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

这很最小割。直接根据式子反推回建模即可。但会发现还有一个 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