题解【P2944 [USACO09MAR]Earthquake Damage 2 G】

传送门。

$\texttt{Description}$

给定一张图，固定一些点，求最小割。

$\texttt{Solution}$

如果没见过这个套路，分析一下也很容易做出来。

题意已经不是割边，而是割点了，考虑拆点，对于每一个点拆出两个点 $u$ 和 $u'$。，这样就能表示出对于点的限制。

若一个点是固定的，那么连 $u\to u'$，容量为 $\infty$，最小割不会割掉容量为 $\infty$ 的点。$1$ 号点同样也需如此处理，因为 $1$ 不会被割掉。

没固定的点直接连 $u\to u'$，容量为 $1$。

对于原图上的边，是不会被割掉的，连 $u'\to v$，由于是双向边，连 $v'\to u$，容量均为 $\infty$。

然后源点连 $1$，每个点的出点连 $t$，容量同样为 $\infty$。

之后求最大流即可。