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...
评论 (0)
