【线性规划与网络流24题】太空飞行计划问题

听说这个模型叫做最大权闭合图,胡伯涛神犇的论文里面有很好的讲解。

最大权闭合图:一张图,有一些点和一些有向边,求其中一个权值最大的闭合子图。闭合图为图中所有点的所有出边仍指向图内的图。

 

虽然不是很会证明。。这个模型可以理解为:每一个点有一些出边,这个点被选了就一定要选出边上的点,怎么选点使得点的权值最大。(感觉有点像2-SAT?不过这个应该不会出现强连通分量

那么这个模型的一般解法:源点S向所有正权点连一条容量为该点权值的边,所有负权点向汇点T连一条容量为该点权值绝对值的边,原来的边容量全部为正无穷。那么该图的最小割一定是一个简单割,并且最大权闭合图为在被最小割分开的两个图中S所在部分去掉S的图。

证明:

闭合图权值为所有和S相连的正权点减去所有不和T相连的负权点的绝对值。

割为所有不和S相连的正权点加上所有不和T相连的负权点的绝对值。

把这两个加起来,发现正好是所有正权点的和。

那么用正权和-最小割为最大权。

说点什么

  Subscribe  
提醒