欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

网络流--最大权闭合子图 *

最编程 2024-07-31 20:27:17
...
了解了概念之后,我们如何对这一类问题进行解决呢?
我们构造一个流量网络满足以下条件:
1 存在源点S和汇点T
2 对于所有权值为正的点,连接一条容量为点权,从S到这个点的边
3 对于所有权值为负的点,连接一条容量为点权相反数,从这个点到T的边
4 原图中连接两点的边,在流量网络中用容量为INF的边连接
在最大权闭合图中,有以下性质
1 最小割为简单割:割集的每条边都与S或T关联
我们可以发现,因为中间连接的所有边都是INF的边权,所以不可能成为割边,于是割集的每条边要么和S相连,要么和T相连
2 最小割和S点关联的集合减去S点就是最大权闭合图
定义:
* S连接的割边带来的分割后在T集边权为正的点的权值和S1
* S连接的割边带来的分割后在T集边权为负的点的权值和S2
* T连接的割边带来的分割后在S集边权为正的点的权值和T1
* T连接的割边带来的分割后在S集边权为负的点的权值和T2
根据闭合图的割是简单割,因为和S,T相连的割边的大小和割边中的点在原图中的权有直接关系,那么我们可以得到:割的大小=S1-T2
又因为我们可以发现图中所有的正点权和=S1+T1
所以图中所有的正点权和-割的大小=T1+T2=和S相连的闭合子图的权
所以当割为最小割时,闭合子图权值最大