题解：P7417 [USACO21FEB] Minimizing Edges P

首先发现

f(x)

的信息相当于奇偶最短路，如果只有纯的最短路我们是好做的，把最短路画在数轴上，每个点随便在上一层选一个父亲即可。

两维的，用类似的方法我们画在平面上，令奇偶最短路分别是

x,y

，则我们画在

(\min(x,y),\max(x,y))

上。

由于奇偶性，这个图中只有斜对角存在邻居，而上下左右没有。

按照平面直角坐标系的上下左右来论，一个点要么从左下角转移过来，要么某一维从左上转移，某一维从右下转移。

考虑从左下往右上扫描线，每次把一层点与开头联通，观察一个连通块，两个端点必定可以使用一类边（否则该图无法构造出来），于是变成了一个序列问题：

a_i

表示该位置有多少点，

b_i

表示该位置能否使用一类边，我们把每个

a_i\ge 1

的连续段拉出来单独处理。

考虑所有

b_i=0

的空腔，这里面的每个点都必须要连向两侧，所以贡献是

a_l+a_r+\sum_{i=l}^{r-1}\max(a_i,a_{i+1})

。

解决了这些点后，有一些点已经被自动解决了（例如 $b:[1,0,0,1,0,0,1]$ ，中间的那个位置有一部分点就被解决了），而剩下的点要解决它们至少需要 $1$ 的代价，而我们刚好可以用 $1$ 的代价（直接使用一类边），所以代价是方便计算的。

这个分析是错误的，错在“至少需要

1

的代价”，事实上对于一个

0111110

（假设有

x

个

1

）的连续段，在处理完

0

后，我们有

\min a

次机会，花费

x-1

拯救

x

个点。

注意序列的最右端不太一样，一个点的右下角可以不在

x\le y

的图上，例如

(a,a+1)

可以与自己相互转移，所以如果使用二类边，向右下的边只需要

\lceil\frac{ num}{2}\rceil

条边即可，一类边仍然需要

num

条。

不过

1.5>1

，最右边的边界情况只能说明，有现成的左边界能用那我们就用，用不了我们就还是用一类边。

所以我们从左往右扫描，传递二类边即可，最后剩下的点用一类边补齐。

一个很重要的误区是：

1

号点必定在第一层（这是因为

1\to dis_p(x)

和

dis_{\neg p}(x)\to 1

的道路是对偶的），但第一层点并不一定只有一个，满足

x=0

的点只有一号点，它只需要转移

y

而无需转移

x

，其他点仍需要从两边转移过来。

（如果第一层点只有一个的话，那之后的每层都只能有一个了。）

文章操作