网络流

201

网络流


如果城市s有一定的货物,每条路能够运送的货物都有一个上限。


将货物从运送到从s送到t就构成了网络流问题


最大流



尽可能把最多的物品从s送到t,除了s、t之外的节点都只是中转。


其有如下性质

  • 容量限制:f(u,v)<=c(u,v)
  • 斜对称性:f(u,v)==-f(v,u)
  • 流量平衡:除s、t外任意节点u,其向外的总流量为0

增广路算法



从零流开始不断增加流量,保证每次增加流量后都满足三个条件。

计算每条边上容量和流量之差(残量),得到残量网络

每条从s到t的一条路径都为原图的增光路,求出该道路中残量的最小值d,把所有边流量加上d即可(增广)

有Edmonds-Karp算法(BFS)


最小割最大流定理



在一个有权图中,源点为Vs,汇点为Vt,从Vs到Vt有很多路径可以走,每条路径都包含若干条边。

这些边可能只属于一条路径,也可能同时出现在两条路径中。

如果拿掉这张图中的一些边,就无法从Vs到达Vt,这些边的组合就叫做割集。



最小割集流量之和=最大流




最小费用最大流



当每个边存在费用,还要考虑费用问题

有以下性质:

只要初始流是该流量下的最小费用可行流,则其增广后的新流还是新流量吓得最小费用流


也即优先填充最小费用的边。



二分图匹配


把节点分成两部分X和Y,使得每条边恰好一个在X一个在Y。

无权图



求包含边数最多的匹配(二分图的最大基数匹配)

增加源点s和汇点t

从s向所有x点,y点到t连接一条容量为1的弧

将每条边变为由x指向y的有向弧,容量为1

求出s到t的最大流

此时流量为1的弧对应了最大奇数匹配

有权图



求边权之和最大的匹配

完美匹配



所有点都被匹配

为每条边加上权值相反数的费用

求最小费用最大流

非完美匹配



不用所有点都被匹配

在求解最小费用流时,记录下流量为0,1……时的最小费用流
发布评论
  • 点击查看/关闭被识别为广告的评论