做网络流24题时感觉就是对建图能力的挑战，本来应该好好整理一下的，奈何时间不足，尽在此简述一下。
一开始做这题时想了另外一个建图方式，但实际上是我读错题目了。这题只要求净收益最大，而不要求所有实验都需要进行。只关心收益的情况下，我们就可以考虑一种合适的建图方法，仅以钱为权重。这里就可以使用闭合图模型。
看见闭合图这个名词，相比很多人都会以为是含有一个很大的环的图（你懂的），但事实上并不是。
定义一个有向图 G = ( V , E ) G=(V,E) G=(V,E)的闭合图（closure）是该有向图的一个点集，且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。按照上面的定义，闭合图是允许超过一个连通块的。
那么对于带点权图，就产生了一个重要的概念——最大权闭合图，即点权和最大的闭合图。
如果我们把赞助商/实验看成一个正权点（增加相应的金钱），把仪器看成一个负权点（花去相应的金钱），并让实验连一条有向边指向该实验需要的仪器，则样例可绘图如下（由于Mermaid功能有限，故使用A/B表示编号为A的点权值为B）：
可以看出，上图的闭合图有 { 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 ∞。
我们所求的最大权闭合图权值和即为所有正权边和-最小割，也就是所有正权边和-最大流。在本图中，最大流为 18 18 18，最大权闭合图权值和即为 35 − 18 = 17 35-18=17 35−18=17。
笔者在此无力证明最大权闭合图为何可以转化为最小割问题，若有读者想了解，可参考Amber的论文《最小割模型在信息学竞赛中的应用》。
在许多实际应用中，给出的有向图常常是一个有向无环图（DAG），闭合图的性质恰好反映了事件间的必要条件的关系：一个事件的发生，它所需要的所有前提也都要发生。一个常见的例子就是制定大学的选课计划，其中一些课程需要以另一些课程为基础，这就是给出了有向无环图。若给所有课程打分，最大权闭合图对应了获益最大或效率最高的选课计划，解决了这个问题，就可以容易地选出一个最合理的选课计划。
在另外一些实际应用中，给出的是一个一般有向图，即有可能出现圈。常见的例子就是工程分期，一个工程可能含有很多项目，项目之间也有依赖关系。有些项目是需要同期一起开发，互相依赖的（即出现圈）。这样，也可以利用最大权闭合图，将最先应该完成的项目选出来作为工程的第一期。
《最小割模型在信息学竞赛中的应用Applications of Minimum Cut Model in Informatics》
昨天刚过完程序员节，相信大家都收到很多礼物吧？狗哥呢，今天还要送两个礼物第一个呢，介绍一个新的大佬：程序员大咖，下面我来说一下我为什么要把TA介绍给大家：（第二个礼物看公...
一、关于SDSoC2017.2安装 所提供的工具链包含32位可执行文件，需要当前Linux系统安装支持32位的兼容库。 在Ubuntu上，32位兼容库可以通过成为超级用户（或root）具有root访问权限后来安装并运行一下命令。 sudo dpkg --add-architecture i386sudo apt-get updatesudo apt-get install...
RxFFmpegRxFFmpeg 是基于 ( FFmpeg 4.0 + X264 + mp3lame + fdk-aac ) 编译的适用于 Android 平台的音视频编辑、视频剪辑的快速处理框架，包含以下功能（视频拼接，转码，压缩，裁剪，片头片尾，分离音视频，变速，添加静态贴纸和gif动态贴纸，添加字幕，添加滤镜，添加背景音乐，加速减速视频，倒放音视频，音频裁剪，变声，混音，图片合成视频，视频...
1、POI使用详解1.1、什么是Apache POI？POI是Apache软件基金会用Java编写的免费开源的跨平台的 Java API，Apache POI提供API给Java程序对Microsoft Office格式档案读和写的功能。POI为“Poor Obfuscation Implementation”的首字母缩写，意为“简洁版的模糊实现”。1.2、POI的jar包导入使用poi需...
在系统——软件包——配置中替换掉之前的原件源，旧软件源已失效
Halo, 看客老爷们大家好, 今天我们的主题还是聊天室, 那么我们这次的聊天室会有什么不同呢! 相信大家看标题就能看出来了, 没错!我们这次的聊天室添加了私聊功能!为什么添加了私聊功能我们需要重新写一篇博客来讲述,且听我道来! 只有群聊的聊天室里,我们只需要客户端向服务端发送信息,服务端接受信息,并向所有客户端反馈接受到的信息,逻辑非常的简介明了,看似添加私聊功能...
在QT开发上位机与单片机通信时，因通信协议包的数据类型有“char”和“float”类型，特此记录。协议包类型如下：typedef struct{ char data1; char data2; char data3; char data4; char dataGroup[5]; float value; char data7;}Dat...
主目录 /drivers/input核心代码 /drivers/input/input.cevent代码 /drivers/input/evdev.c 子设备：按键/drivers/input/keyboard触摸/drivers/input/touchscreen摇杆/drivers/input/joystick鼠标/drivers/input/mouse
常用点状地物： 路灯高程点建筑出入口电杆电塔点状地物绘制方法：（选择地物属性编码，点击画点工具，直接在相应位置点击鼠标左键即可绘制相应地物符号）常用线状地物：围墙道路陡坎电线地类界线线状地物绘制方法：（选择地物属性编码，点击画线工具，直接根据地物走向在各个转折点位置依次点击鼠标左键即可绘制相应地物符号）shift+Z可以改变地物方向常用面状地物：房屋水域台阶斜坡常用绘制方法：（选择地...
大连东软信息学院镜像服务器地址: http://mirrors.neusoft.edu.cn 端口：80 sdkmanager --list --no_https --proxy=http --proxy_host=mirrors.neusoft.edu.cn --proxy_port=80
最近米老师说了一下博客的问题，然后我又认真看了看自己写的博客，发现自己写的博客没有自己的思想，把博客当成了笔记本，把学到的知识往上边一贴就完事了，这种现象非常普遍，而且特别严重，所以如何写博客是一个需要认真思考的问题。下面我们来想一下以下几个问题。 1、博客是什么 通俗点讲，博客就是日志，也就是日记。 2、博客用来干什么 这就要说到博客的作用了。总的
<input type="button" value="隐藏" id="btn"><div id="box"></div>#box { width: 200px; height: 200px; background-color: red;}.show { display: block;}.hidden { display: none;}// 获取元素var btn = document.getElementById('btn');var