自动搬运

查看原文

来自洛谷，原作者为

	masonpop .

搬运于2025-08-24 22:54:58，当前版本为作者最后更新于2024-02-05 17:04:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解太神了，我就补几张图吧。

先不考虑那个补偿费，那么就是一个贪心。转换成网络流模型可以这样：对于左部点 $i$，连出一条长为 $k_i$ 的链，边权分别为 $c_{i,1},c_{i,2},\cdots,c_{i,k_i}$。对于右部点同理，只不过边权反过来，为什么反过来之后会解释。对于每个链尾点，向汇点连边权 $\infty$ 边。这种情况下，最小割就是答案。

考虑什么情况下需要补偿费。对于两条对应边 $(x_i,y_i)$ 和 $(x_j,y_j)$，设链上断掉的边是第 $w_i,w_j$ 条。如果 $\max(x_i,y_i)>w_i$ 且 $\max(x_j,y_j)>w_j$，那么就需要支付费用。发现这个过程非常像切糕里面的额外限制。我们直接把这 $y_j$ 和 $x_i$ 连 $z_i\times z_j$ 的边。如果不懂可以看图：

这样的话，为了使这条路径不连通，只有三种途径：$w_j$ 很大，$w_i$ 很大，或者断掉绿边并付出 $z_i\times z_j$ 的代价。正好符合题意。

建出图后跑最小割即可。代码。