自动搬运

查看原文

来自洛谷，原作者为

	Jorisy 之所以能够离去而义无反顾 / 仅因我记得你已厌倦的梦 / 连最后的道别都稀薄的风中 / 用加倍的叛逆做出抗争

搬运于2025-08-24 22:08:51，当前版本为作者最后更新于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$ 跑最小费用最大流即可。