Preliminaries:
最大流相关算法
首先引进一条定理:一张网络的最小割等于最大流;原因:显然的。
如不明割的概念,请跳到(伪3)最小割↓
1.最大权闭合图
若有向图G的子图V满足【V中顶点的所有出边均指向V内部顶点】,则称V是G的一个闭合子图。其中点权和最大的闭合子图称为有向图G的最大权闭合子图,简称最大权闭合图。
构图方法:添加一个源s,由源向所有正权点连边,容量为权值,增加一个汇t,所有负权点与t连边,容量为点权的绝对值,对于原图中的边,容量改为无限大
定理①:最大权闭合图的点权和=所有正权点权值和-最小割(最大流)。
定理②:上述网络的最小割包含:S到“不在最大权闭合图内的正权节点”的边 以及“在最大权闭合图内的负权节点”到T的边。
定理②的推论:在残余网络中由源点S能够访问到的点,就构成一个点数最少的最大权闭合图。
求解方法:由定理①求得
相关习题:tyvj1452
详情见:胡伯涛《最小割模型在信息学竞赛中的应用》
2.二分图最小点权覆盖与二分图带权最大独立集
一些概念:
点覆盖集:无向图G的一个点集,使得该图中所有边都至少有一个端点在该集合内。
最小点权覆盖集:在带点权无向图G中,点权之和最小的覆盖集。
点独立集:无向图G的一个点集,使得任两个在该集合中的点在原图中都不相邻。
最大点权独立集:在带权无向图G中,点权之和最大的独立集。
二分图最小点权覆盖:二分图上最小点权覆盖集
构图方法:增加源s向集合X连边,容量为点权,增加汇t与Y集合连边容量为点权,X集与Y集边容量改为无限大
求解方法:由某定理(最小点权覆盖权和等于最大流)可求得
二分图带权最大独立集:二分图上点权和最大的独立集
构图方法:如上
求解方法:显然,对于图中任意一个割,将割中的边对应的节点删除就是一个符合的解,于是只要求出最小割就行了,答案为所以权和-最小割容量(最大流)
相关习题:hud1569
(伪3)最小割
以下摘自百度百科:
割:设Ci为网络N中一些弧的集合,若从N中删去Ci中的所有弧,即:使得从顶点Vs到顶点Vt的路集为空集时,称Ci为Vs和Vt间的一个割。
最小割:图中所有的割中,边权值和最小的割为最小割。
构图方法:。。
求解方法:。。
3.二分图的多重匹配
二分图最大匹配已经很熟悉了在二分图最大匹配中,每个点(不管是X集点还是Y集点)最多只能和一条匹配边相关联
二分图的多重匹配就是有一个点可以与多条边有关联,但有上限,记为Li,为点i能有Li条关联边
对于最大匹配(暂不管最优匹配)
构图方法:添加一个源s与X集连边,对于第i个点,连出的边容量为Li,增加汇t,连法类似,对于原来的边,容量改为1,其余不变
求解方法:在构出的网络上跑最大流即可
相关习题:poj1698
4.最大密度子图
给出一个无向图,找一个点集,使得这些点之间的边数除以点数的值(称为子图的密度)最大
构图方法:把原图中的无向边换为两条无向边,容量为1,增加一源点s,向所有点连边,容量为边数m,增加一汇点,与所有点连边,容量为m+2g-dv(g为二分值,dv为v的度)
求解方法:二分枚举最大密度g,然后判断(m*n-MaxFlow)/2>=0,最后跳出的L就是最大密度。拿这个L再重新建图,求最大流,然后从s出发bfs或者dfs,走残留容量大于0的边,所有能到达的点就是答案。
相关习题:poj3155
loading...