Description
有N个工作，M种机器，每种机器你可以租或者买过来.每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。现在给出这些参数，求最大利润
Input
第一行给出N,M(1<=N<=1200,1<=M<=1200)下面将有N块数据，每块数据第一行给出完成这个任务能赚到的钱(其在[1,5000])及有多少道工序接下来若干行每行两个数，分别描述完成工序所需要的机器编号及租用它的费用(其在[1,20000])最后M行，每行给出购买机器的费用(其在[1,20000])
Output
最大利润
Sample Input
2 3
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110
Sample Output
50 首先考虑题目，机器有费用，任务有回报，很容易想到最大权闭合图。 但是有租借的机器，就显得很麻烦。 转回头想，先考虑问题的简化版，即没有租借机器的情况。显然是s->机器连权值为cost的边，任务->t连权值为利润的边，机器向任务连一条正无穷的边，表示任务对机器有依赖关系。(与NOI2006profit一样) 这样一个最小割就是最小花费，然后sigmaprofit-flow就是最大获利。 转过头来看这道题，发现机器不一定是一定要买，可以租，换种思路想，如果不买机器，那每次做一个需要机器的任务需要的费用就是 这个机器租借的费用，那么很简单了，将正无穷的边权改为租借的费用就够了。 其实还可以直接用最小割考虑： 若机器与s在同一集合，则需要的代价就是购买机器的代价，体现在割边上； 若机器与s在同一集合，任务与s不在同一级和，则需要的代价就是租借机器的代价，体现在割边上； 若任务与s在同一集合，则需要的代价就是不要这个任务的代价，也体现在割边上； 至此，解决此问题；
原文链接：https://www.f2er.com/javaschema/285881.html