2021 CSP 题解
T4 交通规划
前言
考场上想到了 $45$ 分暴力的写法,但码力太蒻了,最后没有调出来。
题面简述
给定一个网络和 $T$ 次询问,每次询问给出 $k$ 个附加点的相邻点,
附加点都在 网格边缘以外,并和边缘的一个节点相连,给出其 边权 和附加点的 颜色。
求线段上 端点异色的边 的边权之和。
k <= 2 的解法
(对偶图求最短路) $O(n)$
对于 $k < 2$,只有一个附加点,故连通块颜色相同,则答案为 $0$
对于 $k = 2$ 若两附加点颜色一致,连通块颜色相同,则答案为 $0$.
否则,这个图上会有 一黑一白两连通块。
下图对应本题的样例(借一张图)
红线经过的边权为 $3 + 4 + 5 = 12$。
现在,我们的问题转化成了:在这张图上找一条线,使得这条线把这张图分为两块,并且 线上的边权之和 最小
这是一张 偶图,即把 格子看作 点,然后把 格子之间隔着的边 变为 连接两个格子的点的边
由图可见,起点 和 终点 分别位于两个 附加点 连成的长方形的 两侧,
这是因为一条 分割线 一定经过 两个附加点的不同侧,否则无法把它们两个分开,所以两个点必须在不同侧。
最后,用 $Dijkstra$ 算法求 起点 到 终点 的最短路即可
期望得分:45 分
算法二
(对偶图求最短路 + 区间 Dp) $O(\sum (k_i)\cdot mn\log(mn)+\sum (k_i^3))$
以下内容有亿点点复杂,水平不足者请就此打住,您已经拥有 $345$ 的高分了。
迈出勇敢的一步 k = 3
让我们改一下样例(没错,又是蹭图
可见,在 $(1, 1)$ 位置的点 往左延伸 出一个附加点。
因为点被染上的颜色只有 黑白两种,所以必然可以找到两个同色点,
那么我们可以把这两个点当成 同一个点 进行处理:
这样,我们就知道了 起点 和 终点 的位置!
虚线连接的是除了 起点和终点 以外的所有 同侧边上的点。
问题解决。
问题扩展 k > 2
通过上面的 $k = 3$ 的情况,我们发现我们可以将所有 相邻的同色附加点 合并,将它们 看为一个点
如果有好多点,又该如何处理呢?
上图中,黑色的是原图,红色的是我们转化后的 对偶图。
我们现在要做的,就是把图上的 异色 附加点 两两配对 为 起点和终点,让所有点都有自己的 伴点。
最后,将 可以两两配对的异色点 的 最短路径上的 所有边的权值之和相加即可。
那么,我们该如何配对这些点呢?
如果是直接直接枚举 所有配对方案,那么时间复杂度会飙升到 $O(k!)$,无法接受!
我们需要找到一些性质,来降低枚举的方案数量,也就是 可行性剪枝。
思考一下,异色的附加点 两两配对 后 最短距离和最小 需要满足什么样的性质?
有 $A, B, C, D$ 四个可配对的点,顺时针摆放后 若按 $(A, C)、(B, D)$ 顺序配对,会造成如下情况:
因为它们是交叉着配对的,其最短路必定在一个位置相交,棕色的点就是其相交处。
如此,我们会惊讶的发现,要是将 $(1, 2)、(3, 4)$ 进行配对呢?
如图可见,最终答案显然要优于上一种。
由此,我们总结出了一个规律:配对的点 组成的最短路 不能交叉!
哎,这个规律好熟悉呀,不就是括号序列嘛!
举个例子:若 $A$ 为合法的括号序列,则 $AA、(A)$ 都合法。
那我们要枚举的 配对方案 和 括号序列的方案 一一对应。
于是,我们求出求出 任意两个 起点、终点之间的最短路。
最后用区间 $Dp$ 求出 配对方案中 最小权值之和。
因为这个序列构成一个环形,所以,我们需要 断链加一倍 来实现。
至此,我们实现了所有的操作:
一、 建出 转化后的图
二、 求出 任意两个 起点、终点之间的最短路
三、 用 括号序列 的区间 $DP$ 操作求出 最小值
结语
$AcWing$ 这道题上的评测好像有点问题,其它网站上过了的代码,常数大的在这也过不了。