专题:最大权闭合子图
xiaoh 2020-4-6
问题描述
给定一张有向简单图,每个点都含有一个可正可负的权值.要求选一些点,满足若一个点被选择了,那么所有它可达的点都必须被选择,求所有选中权值和的最大值.
思路
考虑使用网络流进行解决.我们建立超源和超汇,超源与所有正权的点连一条流量为点权的边,超汇与所有负权的点连一条流量为点权的相反数的边,其余图内的点都为正无穷,跑最大流最小割,则答案为正权和-最小割
证明
先考虑最小割算法得出结果的最优性.由于图内的点为,所以最小割显然不会选择这些边作为截断的边.考虑割掉一条边的意义,割掉超源的点表示不要这个点,而割掉超汇则表示要这个点(注意这里,构造的非常巧妙).而跑下来的流量即为(不要的正权和-要的负权和)的最小值.再用总的正权和去减一下显然即为答案.
接下来考虑使用最小割的正确性.若原图仍然联通则说明至少有一个正权点,它的某个后继没有被选中,显然这是不符合题设的,所以原图必须不连通,因此证明了可以使用最小割的正确性.
差评题QAQ例题
网络流题之太空飞行计划问题(数据格式差评)
POJ2987-Firing(OJ界面差评)