网络流24题之太空飞行计划——最大权闭合图转最大流模型_Visors的博客-程序员宅基地

技术标签: 算法  acm  网络流  

做网络流24题时感觉就是对建图能力的挑战,本来应该好好整理一下的,奈何时间不足,尽在此简述一下。

一开始做这题时想了另外一个建图方式,但实际上是我读错题目了。这题只要求净收益最大,而不要求所有实验都需要进行。只关心收益的情况下,我们就可以考虑一种合适的建图方法,仅以钱为权重。这里就可以使用闭合图模型。

闭合图不是环

看见闭合图这个名词,相比很多人都会以为是含有一个很大的环的图(你懂的),但事实上并不是。

定义一个有向图 G = ( V , E ) G=(V,E) G=(V,E)的闭合图(closure)是该有向图的一个点集,且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。按照上面的定义,闭合图是允许超过一个连通块的。

那么对于带点权图,就产生了一个重要的概念——最大权闭合图,即点权和最大的闭合图。

如果我们把赞助商/实验看成一个正权点(增加相应的金钱),把仪器看成一个负权点(花去相应的金钱),并让实验连一条有向边指向该实验需要的仪器,则样例可绘图如下(由于Mermaid功能有限,故使用A/B表示编号为A的点权值为B):

1/10
2/25
3/-5
4/-6
5/-7

可以看出,上图的闭合图有 { 1 , 3 , 4 } \{1,3,4\} { 1,3,4}, { 2 , 4 , 5 } \{2,4,5\} { 2,4,5}, { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} { 1,2,3,4,5},它们的权值和分别为 − 1 -1 1, 12 12 12, 17 17 17,最大权闭合图为 { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} { 1,2,3,4,5},权值和为 17 17 17,正好是我们本题需要求解的结果。

那么有什么好的方法可以用来求最大权闭合图呢?

最大权闭合图转最大流

我们可以在原图的基础上增加源 s s s和汇 t t t,然后让 s s s连向所有正权点,边权为正权点的权值;让所有负权点连向 t t t,边权为负权点权值的绝对值;最后让原来图中的边权全为 ∞ \infty

10
25
INF
INF
INF
INF
5
6
7
0
1
2
3
4
5
6

我们所求的最大权闭合图权值和即为所有正权边和-最小割,也就是所有正权边和-最大流。在本图中,最大流为 18 18 18,最大权闭合图权值和即为 35 − 18 = 17 35-18=17 3518=17

笔者在此无力证明最大权闭合图为何可以转化为最小割问题,若有读者想了解,可参考Amber的论文《最小割模型在信息学竞赛中的应用》。

最大权闭合图模型的应用场景

在许多实际应用中,给出的有向图常常是一个有向无环图(DAG),闭合图的性质恰好反映了事件间的必要条件的关系:一个事件的发生,它所需要的所有前提也都要发生。一个常见的例子就是制定大学的选课计划,其中一些课程需要以另一些课程为基础,这就是给出了有向无环图。若给所有课程打分,最大权闭合图对应了获益最大或效率最高的选课计划,解决了这个问题,就可以容易地选出一个最合理的选课计划。

在另外一些实际应用中,给出的是一个一般有向图,即有可能出现圈。常见的例子就是工程分期,一个工程可能含有很多项目,项目之间也有依赖关系。有些项目是需要同期一起开发,互相依赖的(即出现圈)。这样,也可以利用最大权闭合图,将最先应该完成的项目选出来作为工程的第一期。

参考资料

《最小割模型在信息学竞赛中的应用Applications of Minimum Cut Model in Informatics》

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Visors/article/details/108902403

智能推荐

netty : Max frame length of 65536 has been exceeded._九师兄的博客-程序员宅基地

1. 背景netty刚刚学的io.netty.handler.codec.CorruptedFrameException: Max frame length of 65536 has been exceeded. at io.netty.handler.codec.http.websocketx.WebSocket08FrameDecoder.protocolViolation(WebSoc...

Unity简单AI编写_叫我冷场王的博客-程序员宅基地

开发环境Window7Unity3D  3.4.1MB525defy   Android 2.2.1         羽化的第十二篇博客。最近心情挺好,开始看C#了-0- 为了进一步巩固Unity,当你学了一个计算机语言再学另一个语言发现其实很容易,计算机语言都有很多共通之处,现在学C#真有点原来写VB的感觉,想想时间过得真快啊,已经毕业4个月了,自己到底成长了多少

qchart能绘制三维_Qt开发技术:QCharts(三)QCharts样条曲线图介绍、Demo以及代码详解..._weixin_42510731的博客-程序员宅基地

前言红胖子,来也!按照顺序,本章为样条曲线图。补充QCharts所有的图表都依赖《Qt开发技术:QCharts(一)QCharts基本介绍以及图表框架详解》中的QChart、QChartView、QLegend、QValueAxis。DemoDemo下载地址样条曲线图概述折线图和样条曲线图将数据表示为一系列由直线连接的数据点。在折线图中,数据点由直线连接,而在样条曲线图中,数据点由样条曲线连接。样...

webpack配置html热更新问题_m0_50876885的博客-程序员宅基地_html 热更新

1.为什么webpack不会对html进行热更新?因为webpack需要监听文件的变化才能进行相应的更新。而监听文件是从webpack配置的入口出发,从而对各个依赖进行更新。而入口的js文件一般不会引入html文件作为依赖,所以不会对html文件进行监听,也就不会对html文件进行热更新。2.解决方法由上可知,要使html热更新有以下两种方法:1)将html文件放到入口文件数组中,如下:module.exports = { mode: 'development', //将html加

ceph-msg-messager|ceph网络通信架构--02_bdview的博客-程序员宅基地

目录 ceph的网络通信 ceph网络通信模式分类 simple框架 message数据格式 Ceph通信模块代码分析 ceph网络通信模块类说明 1. Async通信模块角色 2. Async通信模式 Ceph日志和调试 ceph的网络通信 原文:https://www.dazhuanlan.com/2019/08/21/5d5...

随便推点

无线充电宝效果怎么样,无线充电实用性大吗_ABC1235508的博客-程序员宅基地

现在我们一旦要出门,手机肯定是必不可少的工具之一,可以说离开了手机寸步难行。但是随着手机耗电量越来越快,很难有手机的续航能支撑两天,一般情况下,我们使用一天或者大半天就会产生电量焦虑。那么当我们在外出行充电不太方便,但是手机又恰好没电的时候,我们应该怎么办呢?一个充电宝就可以解决你所有的问题!下面让我们一起来看看实用的无线充电宝吧!一、Nank南卡磁吸无线充电宝POW3Nank南卡磁吸无线充电宝POW3自推出以来,销量一路高涨,广受好评,成为时下最火的磁吸无线充电宝品牌之一。在硬件配置方面,Na

一图看懂FC存储网络架构_金陵大掌柜的博客-程序员宅基地_fc存储

简单给大家讲解一下FC存储网络的架构,一般来说在运维的过程中,使用存储的时候不会是拿之即用,最起码为了性能的提高、安全性的提高都会围绕着存储做一系列的配置,比如将多块磁盘配置成RAID模式,然后这只是完成了第一步,接下来还要对已经配置好的RAID划LUN,然后再将LUN分配给相应的主机才可以。大体上来说,各家的存储的使用基本上都是这样一个流程。 如果对RAID和LUN有了解,下面的注释略过即可!!! 这里我对上面提到的两个名词做一个简单的说明,首先RA...

c语言限定符,C语言的限定符修饰问题_TJNiiiaaann的博客-程序员宅基地

foo(const char **p) {}main(int argc, char **argv){foo(argv)}如果编译这段代码,编译器会发出一条警告信息如下:warning: argument is incompatible with prototype一般情况很多人会认为实参char *s 与形参 const char *p 应该是相容的,标准库中所有的字符串处理函数都是这样的。那么为...

java8 ChronoField日期时间枚举类_五月天的尾巴的博客-程序员宅基地_java 时区枚举

ChronoField是java8提供的一个枚举类,里面定义了很多表示日历的字段,提供基于字段的访问来操纵日期,时间或日期时间, 通过实现TemporalField来扩展标准字段集。

jinjia模板和ajax,Django ajax中如何使用jinja2的标签_LA05hiren的博客-程序员宅基地

我有个作孽的功能,联动查询下拉选择服务器之后,把所符合的内容查询出来,通过ajax回填回去其中ajax代码$('#group_id').change(function () {var group_id = $("#group_id").val();$.ajax({data: {'group_id': group_id, csrfmiddlewaretoken: '{{ csrf_token }}'...

Scrum开发基础知识_「已注销」的博客-程序员宅基地

现在敏捷开发是越来越火了,人人都在谈敏捷,人人都在学习Scrum和XP... 为了不落后他人,于是我也开始学习Scrum,今天主要是对我最近阅读的相关资料,根据自己的理解,用自己的话来讲述Scrum中的各个环节,主要目的有两个,一个是进行知识的总结,另外一个是觉得网上很多学习资料的讲述方式让初学者不太容易理解;所以我决定写一篇扫盲性的博文,同时试着也与园内的朋友一起分享交流一下,希

推荐文章

热门文章

相关标签