P5263 [JSOI2013] 打地鼠 题解

Jorisy · 2024-09-24 16:03:27 · 题解

考虑如何构建费用流模型。

首先可以将两只手看作 A,B 两点。

打 i 地鼠的收益 p_i 可以连边 i\rightarrow i+n，流量为 1，费用为 -p_i，表示打这个地鼠；另外需要连边 i\rightarrow i+n，流量为 +\infin，费用为 0，表示不打这个地鼠。

然后 S\rightarrow A,B，n+1\sim 2n\rightarrow T 跑最小费用最大流即可。