网络流

如果城市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……时的最小费用流