CF1666K Kingdom Partition 题解
Zi_Gao
·
·
题解
一个极度对称优美的做法。
首先观察 ABC，发现 A 和 B 同构，所以尝试把 C 放在中间去考虑。令 x_u 表示 u 的选择，列出对于 u \xleftrightarrow{w} v 一条边，所有 x_u,x_v 的矩阵 W_{u,v}：
\begin{array}{c|ccc}
B & 0 & 1 & 2 \\
C & 1 & 0 & 1 \\
A & 2 & 1 & 0 \\
\hline
& A & C & B
\end{array}
最小割只能解决对于 x_u\leq a,x_v\geq b 的变量增加花费，也就是对于矩阵右下角和左上角加划分，显然无法构造。进一步观察，发现对于把 C 作为坐标轴原点，那么图像就是 |x_u+x_v|：
\begin{array}{r|ccc}
B \, (+1) & 0 & 1 & 2 \\
C \, (0) & 1 & 0 & 1 \\
A \, (-1) & 2 & 1 & 0 \\
\hline
|x_u + x_v| & A \, (-1) & C \, (0) & B \, (+1)
\end{array}
不能直接割所以就只能拆点，最小割只能做 |x-y| 情形，变成这种情况也就是 |x_u-(-x_v)|，所以会那么这个式子可以是 x_u-(-x_v),-(x_u)-x_v，所以考虑对于一个 x_u 用两个点 A_u,B_u，分别表示他在作为 +x_u 和 -x_u 出现的贡献点，那么对于 x_u 选择 -1 也就是把两个点反过来。那么我们钦定：
-
-
-
所以对于 u \xleftrightarrow{w} v 只需要交叉连双向边 A_u \xleftrightarrow{w} B_v,B_u \xleftrightarrow{w} A_v，即可做到当 u,v 同时是 A 或者 B，则会割掉两条边，否则不会，如果其中一个是 C，则只会割掉一条边。
最后考虑如果两个 C 有边，但是一个分配到 S 一个分配到 T 则会把所有边割掉，但是最小割会自动规避掉这种情况，因为显然这样不是最小割。
钦定作为 A 或者 B 就链接 \infty 边钦定选到 S 集合或者 T 集合即可。