P7916 [CSP-S 2021] 交通规划

· · 题解

首先感谢赛时被罚坐 40min 的ak爷愿意教我这道 sb 题。

由于是考试题还是胡一下部分分吧，n,m\le18 是会被卡常的插头 DP，n,m\le100 是一眼被秒的集合划分模型，然后 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 开小了。

补充：记得断环为链。