Description
Solution
他讲得很清楚
将那篇博客中的红色标号为 (0)，黄色为 (1)，蓝色为 (2)，绿色为 (3)。则做法简单地讲，就是每个 (0) 向相邻的 (1) 连边，每个 (1) 向相邻的 (2) 连边，每个 (2) 向相邻的 (3) 连边，每个 (3) 向 (T) 连边。（显然每个 (1) 只有一个相邻的 (2)，每个 (2) 也只有一个相邻的 (1)。）当 (S) 与 (T) 不连通时，原图不存在一条 (0-1-2-3) 的路径，故求这张图的最小割即可。
这种题一般是先写个 (n^2) 网络流，然后感觉一下是正解，信仰一波就过了…… 其实分层图跑 Dinic 应该就是很快，貌似和二分图跑 Dinic 的时间复杂度差不多，都是 (O(nsqrt{n})) 的？不会证。。