P4177 [CEOI2008]order
题意：
有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数，求最大利润。
题解：
- 看题意很容易想到最大权闭合子图 但是这题多了一种租赁器材的方式
- 考虑最大权闭合子图的含义 可以看作与s联通表示选择该实验（所以割去器材花费） 与t联通表示放弃该实验（割去实验利益）
- 注意到实验连器材的边为inf 表示不可割去 这题租赁的含义恰巧就是该边的容量变为租赁费用
View Code