最大流类

orz hhw posted @ 2018年7月05日 01:26 in 算法学习 with tags 模板 网络流 算法学习 , 85 阅读

类型说明:基于Edge类,Edge类存储最大流中的边(x,y,nxt,cap),表示一条从x到y流量是cap的边,在邻接表中下一条边的标号是nxt。使用vector<Edge>来存储网络流中的边即可。

Dinic算法

每次在当前的残余网络上进行BFS,将图分层,然后进行DFS,每次要走的增广路必须在残余网络上且层数依次上升$1$,直到没有增广路为之。不断进行BFS+DFS操作直到没有S到T的增广路为止,时间复杂度$O(N^2M)$。加一个当前弧优化,走过的边不再走,可以有效提升代码效率。

Dinic算法在单位权值的图中效率较高,时间复杂度为$O(M\min(\sqrt{M},N^{\frac{2}{3}}))$。Dinic在二分图上效率也较高。

ISAP算法

先使用BFS从$t$开始对图分层,给每个点一个标号$d[x]$,当$d[s]\geq n$时,残量网络中$s,t$不连通,算法结束。

从$S$出发,假设当前走到的节点为$u$,则:

1、如果$u=T$,进行增广,更新答案,然后令$u=S$,进行新一轮的查找;

2、如果在残量网络中存在一条边,使得$d[u]=d[v]+1$,则前进到点$v$;

3、否则对点$u$进行重标号,令$d[u]=min\{d[v]+1\}$

GAP优化:记录$nb[i]$表示有多少点的$d[x]=i$,如果$--nb[d[u]]==0$,那么可以直接退出

时间复杂度$O(N^2\sqrt{M})$,一般来说比Dinic快

最小割集

从$S$出发,在残量网络上走到的所有点属于$S$集,其余点属于$T$集。如果要判断最小割集是否唯一,那么从$S$和$T$出发在残量网络上各走一遍,判断是否所有点都走到过即可。

无源汇有上下界可行流

定义udEdge类,udEdge是一个边集$\{x,y,mi,mx\}$,表示一条从$x$到$y$最小流量$mi$最大流量$mx$的边。

在最大流类$G$中加边$(x,y,mx-mi)$并新建$SS$和$TT$,对于所有点连边$(SS,i,du_i)$或$(i,TT,-du_i)$使流量守恒。

以$SS$为源,$TT$为汇求一次最大流,如果这个最大流能使所有$SS$和$TT$的连边满流就有可行流,此时的流量加上最小流量为方案。

有源汇有上下界最大可行流

增设一条边$(T,S,+\infty)$,用无源汇有上下界可行流的方法判断是否存在可行流。然后去掉$SS$和$TT$,以$S$为源点,$T$为汇点求一次最大流即为最大可行流。

有源汇有上下界最小可行流

同样增加$SS,TT$和一些边,跑一边最大流,增设$(T,S,+\infty)$这条边后再跑一遍最大流。

如果所有新增边满流,则存在可行流,$T$到$S$这条边的流量即为最大可行流。

代码

https://github.com/lbn187/Graph-Theory/blob/master/Maximum_Flow.hpp