最大流的算法有很多，有FF算法，EK，Dinic，ISAP等
@[toc]
增广路就是一条从起点，到终点的一条每边容量 - 实际流量>0的路
所有最大流算法的精华部分是引入反向边
利用反向边，给程序一个返回和改正的机会
FF算法
流程：
1.在图上找到一个从源点到汇点的路径（也就是增广路）
2.取增广路上的残量最小值v（也就是流过的路径中流量最小的那一个）
3.将答案加上v
4.将增广路上所有边的残量减去v，反向边的产量加上v
5.重复1~4，直到找不到增广路
struct Edge {
int to, next;
int cap;
} edge[N * N];
int head[N], tot;
bool vis[N], flag;
LL res;
void addEdge(int x, int y, int cap) {
edge[tot].to = y;
edge[tot].cap = cap;
edge[tot].next = head[x];
head[x] = tot++;
edge[tot].to = x;
edge[tot].cap = 0;
edge[tot].next = head[y];
head[y] = tot++;
}
int dfs(int x, int T, int flow) { // dfs求任意路径
if (x == T) {
res += flow;
flag = true;
return flow;
}
vis[x] = true;
for (int i = head[i]; i != -1; i = edge[i].next) {
int x1 = edge[i].to;
if (vis[x1] || edge[i].cap == 0)
continue;
int newFlow = dfs(x1, T, min(flow, edge[i].cap));
if (flag) {
edge[i].cap -= newFlow;
edge[i ^ 1].cap += newFlow;
return newFlow;
}
}
return 0;
}
void FF(int S, int T) { //有增广路就增广
flag = 0;
memset(vis, 0, sizeof(vis));
dfs(S, T, INF);
while (flag) {
flag = 0;
memset(vis, 0, sizeof(vis));
dfs(S, T, INF);
}
}
int main() {
memset(head, -1, sizeof(head));
tot = 0;
res = 0;
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y, cap;
scanf("%d%d%d", &x, &y, &cap);
addEdge(x, y, cap);
}
int S = 1, T = n;
FF(S, T);
printf("%d\n", res);
return 0;
} EK算法
参考博客
详细过程可以看这个博客
在传统的 FF 算法中，利用 dfs 每次找增广路的过程十分繁琐，常常会走冤枉路，此时更新增广路的复杂度就会增加，EK 算法为了规避这个问题使用了 bfs 来寻找增广路，然后在寻找增广路的时候总是向离汇点越来越近的方向去寻找下一个结点。
我简单总结下，其实就是不断找增光路，并且相应的添加反向边，反向边和正向边和为原边的值。比如一个管道流了20，那就增加一个20的反向边。这样就可以从程序一个反悔的机会
经典例图：
如果没有反向边，程序找的话可能会找到1-2-3-4，流量为1，然后就找不到了。但实际上答案为2，因为可以1-2-4也可以1-3-4，答案中并没有走2-3这个边，如果我们走到了咋办？就可以用反向边进行反悔
如图
在我们走完1-2-3-4后，相应的加上反向边（红边），再寻找增广路，可以找到1-3-2-4，这样最大流就是2.而其中我们走过一遍2-3，又走了3-2，两个相当于抵消了，其实就相当于我们根本没走过2和3之间的边，而抵消（或者说是回溯）就是通过反向边实现的。
仔细想想悟一悟
#include <iostream>
#include <queue>
#include<string.h>
using namespace std;
#define arraysize 201
int maxData = 0x7fffffff;
int capacity[arraysize][arraysize]; //记录残留网络的容量
int flow[arraysize]; //标记从源点到当前节点实际还剩多少流量可用
int pre[arraysize]; //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
int n,m;
queue<int> myqueue;
int BFS(int src,int des)
{
int i,j;
while(!myqueue.empty()) //队列清空
myqueue.pop();
for(i=1;i<m+1;++i)
{
pre[i]=-1;
}
pre[src]=0;
flow[src]= maxData;
myqueue.push(src);
while(!myqueue.empty())
{
int index = myqueue.front();
myqueue.pop();
if(index == des) //找到了增广路径
break;
for(i=1;i<m+1;++i)
{
if(i!=src && capacity[index][i]>0 && pre[i]==-1)
{
pre[i] = index; //记录前驱
flow[i] = min(capacity[index][i],flow[index]); //关键：迭代的找到增量
myqueue.push(i);
}
}
}
if(pre[des]==-1) //残留图中不再存在增广路径
return -1;
else
return flow[des];
}
int maxFlow(int src,int des)
{
int increasement= 0;
int sumflow = 0;
while((increasement=BFS(src,des))!=-1)
{
int k = des; //利用前驱寻找路径
while(k!=src)
{
int last = pre[k];
capacity[last][k] -= increasement; //改变正向边的容量
capacity[k][last] += increasement; //改变反向边的容量
k = last;
}
sumflow += increasement;
}
return sumflow;
}
int main()
{
int i,j;
int start,end,ci;
while(cin>>n>>m)
{
memset(capacity,0,sizeof(capacity));
memset(flow,0,sizeof(flow));
for(i=0;i<n;++i)
{
cin>>start>>end>>ci;
if(start == end) //考虑起点终点相同的情况
continue;
capacity[start][end] +=ci; //此处注意可能出现多条同一起点终点的情况
}
cout<<maxFlow(1,m)<<endl;
}
return 0;
} 另一个模板
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=1<<30;
int n,m,s,t;
struct Node{
int v;
int val;
int next;
}node[201010];
int top=1,head[101010];//top必须从一个奇数开始，一般用-1但我不习惯，解释见下方
inline void addedge(int u,int v,int val){
node[++top].v=v;
node[top].val=val;
node[top].next=head[u];
head[u]=top;
}
inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
int inque[101010];//点是访问过里
struct Pre{
int v;//该点的前一个点（从起点过来）
int edge;//与该点相连的边（靠近起点的）
}pre[101010];
inline bool bfs(){
queue<int>q;
memset(inque,0,sizeof(inque));
memset(pre,-1,sizeof(pre));
inque[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(!inque[d]&&node[i].val){//node[i].val==0则已经该路径满了
pre[d].v=u;
pre[d].edge=i;
if(d==t)return 1;
inque[d]=1;
q.push(d);
}
}
}
return 0;
}//是否有增广路
int EK(){
int ans=0;
while(bfs()){
int mi=inf;
for(int i=t;i!=s;i=pre[i].v){
mi=min(mi,node[pre[i].edge].val);//每次只能增加增广路上最小的边的权值
}
for(int i=t;i!=s;i=pre[i].v){
node[pre[i].edge].val-=mi;
node[pre[i].edge^1].val+=mi;
//反向的边的编号是正向边的编号^1
//这就是为什么top开始时必须是奇数
}
ans+=mi;
}
return ans;
}
int main(){
register int i;
n=Read(),m=Read(),s=Read(),t=Read();
int u,v,w;
for(i=1;i<=m;i++)
u=Read(),v=Read(),w=Read(),addedge(u,v,w),addedge(v,u,0);
printf("%d",EK());
return 0;
} Dinic算法
大体是两个步骤：
1.bfs分层（在EK中bfs是用来寻找增广路的）
2.在层次图中dfs增广
3.重复2，直到不能增广
这个分层就是说对图中的每个点进行分层，u的层次是从源点到该点的最短路径，若与源点不连通，层数就是-1
像这个图，分层后就是 { 1 } { 2 , 3 } { 4 }
为啥这样可以优化？
因为之前dfs对于同层的边会重复运算浪费时间，划分从此后，同层次的点不可能在同一条路径里，可以直接排除
也就是先整理后运算和直接运算的区别
#include<bits/stdc++.h>
#define maxn 1000001
#define INF 19260817
using namespace std;
int cnt,cost[maxn],from[maxn],to[maxn],Next[maxn],head[maxn];
int level[maxn];
queue<int>q;
int S,T,n,m;
void add(int x,int y,int z){ //建边
++cnt;cost[cnt]=z;
from[cnt]=x;to[cnt]=y;
Next[cnt]=head[x];head[x]=cnt;
}
bool bfs(){ //bfs分层
memset(level,-1,sizeof(level));
level[S]=0;q.push(S);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i!=-1;i=Next[i]){
int v=to[i];
if(cost[i]!=0&&level[v]==-1){ //如果容量是0||已被更新就不更新了
level[v]=level[u]+1;
q.push(v);
}
}
}if(level[T]!=-1)return true; //如果流不动了就结束dinic
return false;
}
int dfs(int u,int flow){ //dfs找最大流
if(u==T)return flow;
int ret=flow; //记录初始流量
for(int i=head[u];i!=-1;i=Next[i]){
if(ret<=0)break; //如果已经没流了就退出
int v=to[i];
if(cost[i]!=0&&level[u]+1==level[v]){
int k=dfs(v,min(cost[i],ret)); //把能流的都给下一个点
ret-=k;cost[i]-=k;cost[i^1]+=k; //边权更新，剩余流量更新
}
}
return flow-ret; //返回流出的流量
}
int dinic(){
int ans=0;
while(bfs()==true){
ans+=dfs(S,INF); //累加最大流
}
return ans;
}
int main(){cnt=1;
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&S,&T);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,0); //EK一样建边
}
printf("%d",dinic());
}
//dinic时间复杂度:O(n^2 m). Dinic与Ek比较
在稀疏图上，两者差别不大
在稠密图上（二分匹配之类）Dinic的优势会非常明显
算法主要应用
1.裸的最大流
2.二分图的最大匹配：建一个点s，连到二分图的集合A中，建一个点T，连到二分图的集合B中，再将所有的集合A中的点与集合B中的点相连，全部边权设为一，跑一遍最大流，结果即为二分图的最大匹配
3.最小割：在单源单汇流量图中，最大流等于最小割
4.求最大权闭合图：最大权值=正点权之和-最小割
京公网安备 11010502036488号