题解：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