P7916 [CSP-S 2021] 交通规划

首先感谢[赛时被罚坐 40min 的ak爷](https://www.luogu.com.cn/user/42156)愿意教我这道 sb 题。 由于是考试题还是胡一下部分分吧，$n,m\le18$ 是会被卡常的插头 DP，$n,m\le100$ 是一眼被秒的[集合划分模型](https://www.luogu.com.cn/blog/ICANTAKIOI/ji-ge-hua-fen-mu-xing)，然后 $k=2$ 是集合划分模型的弱化版，平面图最小割。 这其中给我们启发最大的肯定是有特殊性质的 $k=2$，我们其实在干这样一个事情： 设两个询问点分别为 $x<y$，颜色为 $c_x,c_y$。 如果 $c_x=c_y$ 那么直接染成同一种颜色。 否则一部分染成 $c_x$ 的颜色，另一部分染成 $c_y$ 的颜色，代价是中间的每条边，也就是一个割，求最小就直接上平面图最小割。 考虑为什么是最优的，我们染出来的色是这样的玩意：  其中 $x,y$ 均被钦定为了更有表现力的红色和蓝色。 如果染出来了多种颜色交替，可能形如：  显然我们可以将中间两块颜色翻转，就可以去掉两条割的贡献。 更复杂的绕成圈的贡献肯定也能像这样翻转去掉，最后剩下的一定只形如图 1。 考虑多个询问点：  显然像图中相邻且两段钦定都是红色的我们可以合并成一段，代价为 $0$。 那么这个网格图上被钦定的颜色必定两色交替，且个数为偶数。  那么我们还是考虑画出一条条的线来分割，代价就是所有分割线上的权值和。 首先分割线交叉了可以看作不交叉，看作在接头的地方碰头再分开。  然后不交叉的话，考察钦定颜色相邻的部分，它们一定为偶数。 同时线段一定从这里出发和结束，并且发现这些区域必定由线段构成了两两配对，要证明的话思路大概也同 $k=2$ 的情况。  在两两配对的情况下考虑最优，发现就是区域到区域的平面图最小割，跑最短路即可。 先把配对的最优代价用 Dij 预处理出来，然后做一个区间 DP 来找到最优的配对方式，即可。 复杂度 $O(kmn\log{(mn)}+k^3)$，由于 $nm$ 要开到卡掉网络流的级别，就只能委屈 $k$ 开小了。 补充：记得断环为链。