CEOI 2008 order 另类最大权闭合图-可以有依赖违反代价

发布时间：2020-12-13 23:15:32 所属栏目：百科来源：网络整理

导读：Description 有N个工作，M种机器，每种机器你可以租或者买过来.每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。现在给出这些参数，求最大利润 Input 第一行给出N,M(1=N=1200,1=M=1200)下面将有N块数据，每块数据第一

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

Sample Output

50 首先考虑题目，机器有费用，任务有回报，很容易想到最大权闭合图。但是有租借的机器，就显得很麻烦。转回头想，先考虑问题的简化版，即没有租借机器的情况。显然是s->机器连权值为cost的边，任务->t连权值为利润的边，机器向任务连一条正无穷的边，表示任务对机器有依赖关系。(与NOI2006profit一样) 这样一个最小割就是最小花费，然后sigmaprofit-flow就是最大获利。转过头来看这道题，发现机器不一定是一定要买，可以租，换种思路想，如果不买机器，那每次做一个需要机器的任务需要的费用就是这个机器租借的费用，那么很简单了，将正无穷的边权改为租借的费用就够了。其实还可以直接用最小割考虑：若机器与s在同一集合，则需要的代价就是购买机器的代价，体现在割边上；若机器与s在同一集合，任务与s不在同一级和，则需要的代价就是租借机器的代价，体现在割边上；若任务与s在同一集合，则需要的代价就是不要这个任务的代价，也体现在割边上；至此，解决此问题；

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!