4
7
2015
0

【口胡向·水·存档】网络流构图基础模型

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...

Category: 算法 | Tags: | Read Count: 476988

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com