P10129 题解

masonpop · 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 的代价。正好符合题意。

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