CF1749

E

一个 \(n\times m\le 3\times 10^5\) 的网格，里面有一些 \(1\)，其余是 \(0\)，你需要填上尽可能少的 \(1\)，让网格上下不连通，并且 \(1\) 之间边不相邻。

这道题还是发现我网格图图论不扎实的问题。

首先很容易想到一定会存在一条自左到右的链，分隔了上下两部分。所以我直接从左到右 \(DP\)。

但是得到了 \(WA2\) 的好成绩。

左思右想也找不出问题，但是对拍后发现似乎是可以往回走的。

改成最短路算法就通过了。

矩阵图论的题目，不要只看到自左向右，要考虑存不存在往回的可能。

如果没有错过，确实很难意识到这种思维漏洞，所以一定要记住！