[NOI2020]翻修道路 部分分题解 正解已咕

给定一张带边权的弦图,给定起点终点,求这两点之间不是割集的最短路径的长度。

部分分:所有边权为 11

求出任意一条最短路,如果它合法就输出它的长度,否则输出 1-1。正确性证明:

显然最短路合法就输出一定是正确的。如果最短路不合法,我们找到它的最小的、是割集的子集。由于这是最小割集,它一定把原图分成了恰好两个连通块,而且其中每一条边都横跨了两个连通块。那么有以下几种情况:

  • 这个割集的大小为 11,那么其中唯一的一条边就是原图的割边,起点到终点的任意一条路径都要经过它,于是无解。

  • 这个割集的大小大于 11,且它不连通。我们随便找出其中两条不相邻的边来看,假设这两条边分别是 xuxuvyvy,它大概像这样:(图片来自 matthew99 的官方题解 PPT)

假设 PxvP_{xv}PuyP_{uy} 分别是删掉割集后,xxvvuuyy 的经过的最短路径。那么 Pxv+xu+Puy+vyP_{xv}+xu+P_{uy}+vy 是一个长度至少为 44 的环,这个环上应该有弦,但是不管怎么加弦,要么与割集两边不连通矛盾,要么与 PxvP_{xv}PuyP_{uy} 是最短路径矛盾。

  • 这个割集的大小大于 11,且它连通。和刚才相反,我们随便找出其中两条相邻的边来看。设这两条边是 uvuvvwvw,它大概像这样:

如果 uwuw 之间没有直接连边,假设它们删掉割集后的最短路径是 PuwP_{uw}。那么 uv+vw+Puwuv+vw+P_{uw} 是一个长度至少为 44 的环,和上面类似,不管怎么加弦都要矛盾。我们只能加 uwuw 这条弦。但是如果 uwuw 之间有直接连边,这又和一开始我们找的是最短路矛盾。

综上所述,如果最短路是割集,一定是上面的第一种情况,输出 1-1 一定是正确的。部分分做法到此结束。

正解

它永远地咕咕了。