题解 P7916 [CSP-S 2021] 交通规划

· · 题解

解析

引子，k\leq 2 的解法

对于 k<2，显然可以全部染成附加点的颜色，答案即为 0

对于 k=2，若此时两个附加点颜色相同，显然答案也为 0；

否则整张图一定会被染成一白一黑的两个连通块

（比如这样：）

可以发现原图是一张平面图。特别的，这里认为存在附加点的射线将原本的仅一个 无界面（即那个不在平面图内部，面积无穷大的面）划分为了多个无界面，且对偶图中无界面之间不连边

若我们建出原图的对偶图：对偶图每条边的边权为和它相交的原图的边权。可以发现，答案即为对偶图上两个对应无界面的结点间的最短路

于是对每次询问跑一次 dijkstra 即可。只有无界面对应的结点需要在每次询问时新建。该部分分的复杂度即为 O(Tnm\log(nm))

对于所有数据的解法

由 k\leq 2 部分分做法以及一定程度手玩的启发，可以想到：考虑将相邻的不同颜色附加点射线间的结点两两配对（容易注意到这样的结点个数一定为偶数或 1；结点数为 1 时显然仅存在一种颜色附加点，答案为 0）并分别按 k\leq 2 的做法求最短路，再去掉这些最短路对应的原图的边集，那么答案方案所需要去掉的边集一定为某种配对方案对应的边集

（图中红色结点为需要配对的结点，淡蓝色区域则为该结点对应的无界面：）

按照这个结论能得到一个合法的方案是显然的：如此两两配对后，所有配对结点间的路径一定能将不同颜色的附加点划分到不同的连通块中；若有两条路径存在部分重合，那么交换配对结点一定会有更小的边权和，因此最终得到的方案也不会有路径重合（即不会有重复的需要去掉的边）

但要证明其最优性还需证明答案方案一定为结论所述的形式：即不同色附加点射线间结点两两配对求路径得到的路径集合对应的原图边集；或者换句话说，不存在类似从相邻的同色附加点射线间穿出的路径，或在网格内部断掉的路径这种奇奇怪怪的情况。这可能需要费一点功夫，但大体也就是分类讨论并反证。由于太长，具体内容可见 此处

求路径和最小的配对方案可以 O(k^3) 直接 dp，具体此处略。最终复杂度可以做到 O(\sum (k_i)\cdot mn\log(mn)+\sum (k_i^3))

另外还有一个小细节。求出的最短路可能长这样：

所以对于同色附加点射线间的结点也必须要建点，并和网格内的结点连双向边

CODE

链接