题解：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，其他点仍需要从两边转移过来。

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