【网络流24题】—-题解(部分,持续更新…)

搭配飞行员

搭配飞行员:http://cogs.yeefan.us/cogs/problem/problem.php?pid=14
题解:建立虚拟源点汇点,然后水过
code:http://cogs.yeefan.us/cogs/submit/code.php?id=148410

数字梯形

数字梯形:http://cogs.yeefan.us/cogs/problem/problem.php?pid=738
题解:
规则(1)
把梯形中每一个位置抽象为两个点(i.a),(i.b),建立附加源S汇T。
1、对每一个点i从(i.a)到(i.b)连接1条容量为1,费用为点i权值的有向边。
2、从S向梯形顶层每一个(i.a)连1条容量为1,费用为0的有向边。
3、从梯形底层每一个(i.b)向T连1条容量为1,费用为0的有向边。
4、对每一个点i和下面的两个点j,分别连1条从(i.b)到(j.a)容量为1,费用为0的有向边。
求最大费用最大流,费用流值就是结果。
规则(2)
把梯形中每一个位置看作1个点i,建立附加源S汇T。
1、从S向梯形顶层每一个i连1条容量为1,费用为0的有向边。
2、从梯形底层每一个i向T连1条容量为无穷大,费用为0的有向边。
3、对每一个点i和下面的两个点j,分别连1条从i到j容量为1,费用为点i权值的有向边。
求最大费用最大流,费用流值就是结果。
规则(3)
把梯形中每一个位置看作1个点i,建立附加源S汇T。
1、从S向梯形顶层每一个i连1条容量为1,费用为0的有向边。
2、从梯形底层每一个i向T连1条容量为无穷大,费用为0的有向边。
3、对每一个点i和下面的两个点j,分别连1条从i到j容量为无穷大,费用为点i权值的有向边。
求最大费用最大流,费用流值就是结果。
其实第2个和第3个都很好处理,就是第1个有些麻烦,对这个题,我们建立n排点还是比较好写的

code:http://cogs.yeefan.us/cogs/submit/code.php?id=157717

负载平衡

负载平衡:http://cogs.yeefan.us/cogs/problem/problem.php?pid=741
题解:
首先求出所有仓库存货量平均值,设第i个仓库的盈余量为A[i],A[i] = 第i个仓库原有存货量 – 平均存货量。建立2分图,把每一个仓库抽象为两个节点Xi和Yi。增设附加源S汇T。
1、如果A[i]>0,从S向Xi连1条容量为A[i],费用为0的有向边。
2、如果A[i]<0,从Yi向T连1条容量为-A[i],费用为0的有向边。
3、每一个Xi向两个相邻顶点j,从Xi到Xj连接1条容量为无穷大,费用为1的有向边,从Xi到Yj连接1条容量为无穷大,费用为1的有向边。
求最小费用最大流,最小费用流值就是最少搬运量。

code:http://cogs.yeefan.us/cogs/submit/code.php?id=157626

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【网络流24题】—-题解(部分,持续更新…)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡