最大权闭合子图（模板）

- 日理万妓 2022-09-25 11:26 130阅读 0赞

参考博客：  
http://www.cnblogs.com/kane0526/archive/2013/04/05/3001557.html

http://www.cnblogs.com/wuyiqi/archive/2012/03/12/2391960.html

http://blog.csdn.net/sdj222555/article/details/7797534

http://www.cnblogs.com/vb4896/p/4149107.html

什么是最大权闭合子图：

最大权闭合子图指选择u，则u以下关系的都要选，一定要选到底，不能跳过u选它以下的。增设一个超级源点和一个超级汇点，（1->n）的点中，当点权为正时，从源点向该点连一条权值为点权大小的边，当点权为负时，从该点连一条权值大小为它的绝对值的边连向汇点。这种问题一般都是对于（u，v），如果选择u必须选择v，对（u，v）连一条容量为oo的边。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-do1V4ZCF-1613976889417)(https://img-blog.csdn.net/20160821165905429)\]

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GDYBpKOp-1613976889424)(https://img-blog.csdn.net/20160821170018617)\]

结论：  
最小割为简单割  
闭合图是简单割  
简单割是闭合图  
最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图。  
答案数等于靠近源点最小割一边的点数，最大利益=所有点正权值之和-最小割。

证明参考博客:http://www.cnblogs.com/wuyiqi/archive/2012/03/12/2391960.html

—————————————————————————————

对于一个图，我们可能会有多种割法得到的最大权封闭子图的价值相等。

求所得最大权子图中的所有点：遍历源点能到达所有点，能遍历到说明其点在子图中，什么叫能遍历到呢？就是检查残余网络中的边和反向边，若(u,v)边权大于0，则说明u能到达V。

这样能遍历到的一定是点数最少的最大权封闭子图，证明见:http://blog.csdn.net/sdj222555/article/details/7797534

如何求最多能遍历到一种类型的点在最大价值下最多能有多少个呢，比如有梦想和付出，完成梦想可以得到价值，完成付出需要消耗价值，如何求在得到最大价值的情况下最多能得完成多少个梦想呢。

给所有连接到源点汇点的边权乘一个较大的常数，另给连接到源点的梦想的边权加1，这样弄一遍网络流，得到的最大价值除一个较大的常数就是我们需要的价值，源点能到达的梦想就是最大梦想。

参考博客http://www.cnblogs.com/vb4896/p/4149107.html

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关带权的最大子段和问题

Description 在短学期和算法导论课期间，我们一共讨论了四种求解最大子段和问题的方法，上一届的期末考试也考了交替出现的子段和问题，今天我们再拓展一下，研究一下最大的

「爱情、让人受尽委屈。」/ 2023年02月23日 05:27/ 0 赞/ 1 阅读

相关最大密度子图

最大密度子图一、了解概念首先要了解什么是最大密度子图，顾名思义，就是所有子图中密度最大的那一个。那么什么是一个子图的密度呢，这里规定子图的密度就是子图中边数和点

淡淡的烟草味﹌/ 2022年10月31日 13:48/ 0 赞/ 171 阅读

相关最大权闭合子图

闭合图首先，先了解什么是闭合图。闭合图一般指一个图中点的集合，从该集合中所有的点出发，能到达的点要求都必须在该点集中。也就是说，从该集合中出发，一定要回到该集合中，不能

￡神魔★判官ぃ/ 2022年10月29日 12:29/ 0 赞/ 146 阅读

相关最大权闭合子图（模板）

参考博客： http://www.cnblogs.com/kane0526/archive/2013/04/05/3001557.html http://www.cnbl

- 日理万妓/ 2022年09月25日 11:26/ 0 赞/ 131 阅读

相关最大上升子序列（模板题）

include <iostream> include <cstring> include <algorithm> using name

分手后的思念是犯贱/ 2022年09月13日 14:27/ 0 赞/ 149 阅读

相关 hdoj 4971 A simple brute force problem. 【最大权闭合图 --> 最小割】

题目：[hdoj 4971 A simple brute force problem. ][hdoj 4971 A simple brute force problem.]

素颜马尾好姑娘i/ 2022年08月12日 00:13/ 0 赞/ 165 阅读

相关 NYOJ 104-最大和【模板：最大子阵和】

最大和时间限制：1000 ms | 内存限制：65535 KB 难度：5 描述给定一个由整数组成二维矩阵（r\c），现在需要找出它的一个子矩阵，使得这个子矩阵内

妖狐艹你老母/ 2022年07月24日 08:07/ 0 赞/ 208 阅读

相关 HDU 3061 Battle(最小割----最大权闭合图)

题意： Problem Description 由于小白同学近期习武十分刻苦，很快被晋升为天策军的统帅。而他上任的第一天，就面对了一场极其困难的战斗：据侦查兵

- 日理万妓/ 2022年01月10日 13:25/ 0 赞/ 235 阅读

相关最大权闭合子图

闭合图：对于一个有向图G，存在点集合V，任取点u属于V，u的出边的另一个点也属于V，则为闭合图。最大权闭合子图：当每个点有一个权值w（有正有负），点权和最大的闭合图为

怼烎@/ 2022年01月10日 13:07/ 0 赞/ 221 阅读

相关 bzoj 1497（最大权闭合图/最小割）

[传送门][Link 1] 题意：有$n$个通信塔，建立第$i$个通讯塔需要花费$p\_i$元。同时有$m$个人，对于第$i$个人，如果$a\_i$号塔以及

ゝ一纸荒年。/ 2021年11月05日 13:16/ 0 赞/ 278 阅读