表示“必须选”的模型

题目大意

---

题目分析

一个格子有四种方式看上去很难处理。将横竖两个方向分开考虑，会发现：因为收益只与相邻格子是否连通有关，所以可以将一个格子拆成表示横竖两个方向的，互相独立的点。

 

上图的格子里的红边表示的就是一个格子的可能方向；所连蓝边的容量为1，费用即为连通两个格子的收益。