题解 P2762 【太空飞行计划问题】

更改内容：对建模图有改动 # 题目大意 有$m$个实验，`每个实验只可以进行一次`，但会获得相应的奖金，有$n$个仪器，每个实验都需要一定的仪器，`每个仪器可以运用于多个实验`，但需要一定的价值，问奖金与代价的差的最大值是多少？ # 解题思路 这道题无非是让我们权衡奖金与代价，这两者是有我没他的，怎么去处理呢，我们先建立一张图，所有的实验与源点相连，容量为其奖金，所有的器材与汇点相连，容量为其价格，中间实验与器材相连，容量为无穷大。 这个时候跑最小割，其必定会割掉连接实验或容器的边，因为中间的边的代价为无穷大，一定不会被割掉。 跑最小割相当于选择部分的实验和部分的仪器，剩下的实验和仪器就会被割掉，此时再用实验的总价值减去可能得到的最大值，即为其所要求的答案 如下图  代码这里就不放出了，楼下的题解个个都比本蒟蒻的好，关键还是在于建模