【bzoj1391】【Ceoi2008】【Order】【最小割】
发布日期:2021-11-16 15:38:23
浏览次数:5
分类:技术文章
本文共 770 字,大约阅读时间需要 2 分钟。
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
HINT
题解:源点向每个任务连收益的边,每个任务向它需要的机器连租费的边,每个机器向汇点连价格的边。
用总收益减去最小割即可。
代码:
#include#include #include #define N 3000#define M 1500000#define INF 2100000000using namespace std;int point[N],next[M*2],n,m,cnt(1),k,a,b,c;int dis[N],cur[N],gap[N],pre[N],s,T,sum,mn;struct use{int st,en,v;}e[M*2];bool f;void add(int x,int y,int v){ //cout< <<' '< <<' '< <
转载地址:https://blog.csdn.net/sunshinezff/article/details/50992949 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月17日 08时13分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
唱好铁血丹心谐音正规_趙贤典:打好“感情牌” 唱好“大合唱”
2019-04-21
aix系统vi修改命令_Linux基础知识必备:利用vi编辑器创建和编辑正文文件
2019-04-21
天涯明月刀开发_玩家被天涯明月刀手游“冷落”?六大门派角色竟不带正眼看人...
2019-04-21
this指向undefined uiapp_一个this都没有,真好
2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。
2019-04-21
技校毕业是什么学历_中等职业学校是什么_中等职业学校毕业是什么学历
2019-04-21
2压缩备份数据库_MySQL数据备份与恢复(二) xtrabackup工具
2019-04-21
英特尔cpu发布时间表_被嘲讽的英特尔核显,强大能力其实超乎你的想象
2019-04-21
chi2inv函数 matlab_MATLAB概率和统计(2)
2019-04-21
lisp修改上一个图素_在Windows上安装Haskell
2019-04-21
ad19 导出step 没有pcb_几款主流PCB软件哪个最好用,你用过几款?
2019-04-21
ocdma相干非相干_《Acconeer 60GHz脉冲相干雷达芯片:A111》
2019-04-21
修改表格字体颜色_Excel技巧:Excel如何修改字体颜色
2019-04-21
prism项目搭建 wpf_WPF MVVM使用prism4.1搭建
2019-04-21
python中func自定义函数_Python函数之自定义函数&作用域&闭包
2019-04-21