P7417 [USACO21FEB] Minimizing Edges P

约瑟夫用脑玩 · 2021-05-03 16:39:36 · 题解

换一种方式来解释这道题的贪心可能更好理解一点。

首先我们得知道新图只与函数 f 的值有关，而由于我们可以在一条边上来回横跳，所以 f 是否有值取决于奇/偶最短路的长度，那么我们用 O(n) BFS 出最短路即可。

注意特判一下每个点只有奇数路径或偶数路径，即这是个二分图，那么直接用原图的最短路树就可以表示了。

否则，每个点都会有奇数和偶数路径，设一个点的奇最短路和偶最短路二元组为 (x,y)。

由于顺序并没有关系，且为了好看方便，我们取 x 为奇偶中较短的最短路，y 为较长的，即 x<y。

那么考虑导致 (x,y) 的方式：

• 有另一个点奇偶最短路分别为 (x-1,y-1) ，并连了一条边。

• 有两个点分别为① (x-1,y+1) 和② (x+1,y-1) ，都连了一条边。注意当 x+1=y 时，有 (x+1,y-1)=(y-1,x+1)=(x,y)

解释一下：第二个方式中①的第一维保证较小最短路为 x，②第二维保证了较大最短路为 y，而他们的其他维由于与 (x,y) 的点有直接连边故最大都只能 +1。

第一种方式只用一条边显然血赚，但可能没有 (x-1,y-1) 的点，此时就只能用第二种方式。

所以才出现了如下的贪心方法：

• 按先 x+y 为第一维，再 x 为第二维依次考虑。（下图中纵坐标为倒着的 x+y，横坐标为倒着的 x，故先从上到下，再从右到左依次考虑，也就是把上图往右掰了一点）

• 如果右边 (x-1,y+1) 没有第二种方式的需求传过来，那么 (x,y) 直接选第一种方式。

  否则 (x,y) 的一部分点用于满足其需求，于是还会有需求往左 (x+1,y-1) 传，如果 (x,y) 点数有多余的就还是用第一种方式。

  最后我们会传到 x+1=y 的边界，此时就相当于同类连边不再传了。

  这样看的话，就是将必须用第二种方式的边一直往左传，传到边界用每个点 \frac{1}{2} 的代价消掉，而传时还有 1 的代价，故将本来用 2 的代价减小为 1.5 的代价。

  注意到 1.5<1，故有多余不用传时尽量还是用第一种方式。

和其他题解最后的做法都一样，但思路可能会好理解点qwq。

估计没人看的代码

Upd：修改了一点小锅，以前是对的表述就没改了。（虽然读着有点奇怪）