BZOJ1280 Emmy卖猪pigs题解

2025-08-04

建立超级源点 $s$ 和超级汇点 $t$。对每个顾客和猪圈建一个点。对于顾客 $i$,将 $i$ 与汇点连容量为 $b_i$ 的边。对于🐖圈 $i$,将源点与 $i$ 连容量为 $p_i$ 的边。对于每个 $k_i$,考虑其中的每个猪圈。如果猪圈没有其他顾客来过,则该猪圈往顾客连容量为 $+\infty$ 的边。否则上一次来过的顾客往现在的顾客连容量为 $+\infty$ 的边。最后跑最大流即可。