题解：CF1054F Electric Scheme

· · 题解

显然答案有一个上界是 2n，直接在每个交点出画一个很小的十字即可。考虑减少答案，如果两个十字处在同一个 x 轴或 y 轴上的话，我们就可以将两条横线/竖线合并成一条，因此答案会减少 1，我们希望合并尽可能多的线。

具体来说，对于一个相同的 x/y 轴，我们将在这个轴上的相邻两点之间的横线/竖线合并为一条。但注意到有的时候合并会出现矛盾，有可能会造成额外的交点，这时造成矛盾的两条合并出来的边我们只能选一个。

将边看作点，在出现矛盾的这两条边之间连边。这样原问题就转换成了 O(n) 个点，O(n^2) 条边的最大独立集问题，即一条边的两端点只能选一个，答案就是 2n 减最大独立集。注意到产生矛盾的合并只有行跟列之间的矛盾，因此这是一个二分图。跑二分图最大独立集构造方案即可。

二分图最大独立集正确性说明：

考虑最小割本质在干什么，是要给每个点一个所属集合 S/T，即当成一个布尔变量 x_u=0/1，最小割中的一条边 (u,v,w) 的意义是「若 u 选择了 S，v 选择了 T，则有 w 的代价」，用式子表示就是最小化 \sum\limits_{(u,v,w)\in E}x_u(1-x_v)w。考虑能否把最大独立集写成最小割的这个式子的形式，令 x_u=0/1 代表点 u 最终是否在这个独立集中，则转换成要最大化 \sum x_u-\sum\limits_{(u,v)\in E}x_ux_v\inf，将其取相反数就变成最小化 \sum -x_u+\sum\limits_{(u,v,w)\in E}x_ux_v\inf，再将右部点 x_v 取反，有 \sum\limits_{u\in L}-x_u+\sum\limits_{v\in R}-(1-x_v)+\sum\limits_{(u,v,w)\in E}x_u(1-x_v)\inf，此时后面就变成一个标准的最小割形式了，但是前面的负数不好处理，考虑将式子前面加个 n，即 \sum\limits_{u\in L}(1-x_u)+\sum\limits_{v\in R}x_v+\sum\limits_{(u,v,w)\in E}x_u(1-x_v)\inf，此时可以直接最小割了。对于左部点 u，连 (s,u,1)；对于右部点 v，连 (v,t,1)；对于中间的边，连 (u,v,\inf)。跑完之后拿 n 减去最小割就是最大独立集。注意到这个建模和最大匹配的区别在于中间不是 1 了，但容易发现边权改为 1 对正确性没有影响，因为入出中间点的流量至多就是 1。

有了这个转换，构造最大独立集也变得显然了。由于我们将右部点取反了，那么独立集就是 s 走没被割的边能到的左部点和不能到的右部点。

submission：https://codeforces.com/contest/1054/submission/336707335

有人说这个题很好写，我并不这么认为。/ll