最大流类
类型说明：基于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
评论 (0)
