自动搬运

查看原文

来自洛谷，原作者为

	Ajwallet 厌倦追寻，一觅即中

搬运于2025-08-24 21:41:19，当前版本为作者最后更新于2018-06-23 13:38:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

更改内容：对建模图有改动

题目大意

有$m$个实验，每个实验只可以进行一次，但会获得相应的奖金，有$n$个仪器，每个实验都需要一定的仪器，每个仪器可以运用于多个实验，但需要一定的价值，问奖金与代价的差的最大值是多少？

解题思路

这道题无非是让我们权衡奖金与代价，这两者是有我没他的，怎么去处理呢，我们先建立一张图，所有的实验与源点相连，容量为其奖金，所有的器材与汇点相连，容量为其价格，中间实验与器材相连，容量为无穷大。

这个时候跑最小割，其必定会割掉连接实验或容器的边，因为中间的边的代价为无穷大，一定不会被割掉。

跑最小割相当于选择部分的实验和部分的仪器，剩下的实验和仪器就会被割掉，此时再用实验的总价值减去可能得到的最大值，即为其所要求的答案

如下图

代码这里就不放出了，楼下的题解个个都比本蒟蒻的好，关键还是在于建模