网络流之最大流（入门）【FF+EK+Dinic+ISAP】_综合

参考视频链接

网上关于网络流讲解的视频很少，大多数质量也不是很高，感觉我推荐的这个up主讲解的是最好的（除了音量比较小一点），文章中有一些讲的比较不清楚的地方视频中都讲解得很清楚

【网络流模型】基础知识篇
【网络流模型】FF算法
【网络流模型】EK算法
【网络流模型】Dinic算法
【网络流模型】ISAP算法

基础知识

网络：具有一个出度为0的点s和一个入度为0的点t的有向图，每一条边上有权值
源点：出度为0的点s
汇点：入度为0的点t
容量：边上的权值，用c(u,v)表示
假设需要从s发货到t
流量：实际运送的货物量
① 边上的流量f(u,v)=x 【从u运送x个货物到v】
f(u,v)<=c(u,v)容量限制
f(a,c)+f(b,c)=f(c,t) 流入量=流出量
?u Σ f(i,u) = Σ f(u,j) 流守恒性
② 整个网络的流量:整个网络运送的货物的量即总的发货量
|f|=Σ f(s,v) min=0 max最大流（最多运送货物的总量）~~就是我们需要研究的问题~~
割：一个边集cut，若删去该边集则s与t不连通
|cut| max=所有边数 min最小割~~就是我们需要研究的问题~~
费用流：保证在最大流的情况下考虑费用，最小费用最大流
残量网络Gf : c’(u,v)=c(u,v)-f(u,v) 残留（量）
增广路：从s到t能够增加运货量的路

以下算法的代码模板都是基于P3376 【模板】网络最大流实现的

FF算法

思路分析

怎么求？
在残量网络上不断找增广路，每次增广得到的增广量Δi，则|f|=Σ Δi ，需枚举不同增广方案使|f|最大
用dfs找增广路，回溯时更新残量网络
建后悔边 ?Gf c’(s,a)+c’(a,s)=c(s,a)
更新残量网络正向+Δ 反向-Δ
后悔边的表示e[i^1] (边要从2开始存,2^1=3 3^1=2)

代码

#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll const M=520010;
ll const N=520010;
ll const INF=2005020600;
ll n,m,s,t;
ll cnt=1,head[N],vis[N];
struct edge{ll to,next,cap;
}e[M];
void add(ll u,ll v,ll cap)
{cnt++;e[cnt].to=v;e[cnt].next=head[u];e[cnt].cap=cap;head[u]=cnt;
}
ll dfs(ll u,ll flow)
{if(u==t)return flow;vis[u]=1;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(e[i].cap<=0||vis[v])continue;ll delta=dfs(v,min(e[i].cap,flow));if(delta<=0)continue;e[i].cap-=delta;e[i^1].cap+=delta;return delta;}return 0;
}
ll getmaxflow()
{ll maxflow=0,delta;while(delta=dfs(s,INF)) {memset(vis,0,sizeof(vis));maxflow+=delta;}return maxflow;
}
int main()
{scanf("%lld%lld%lld%lld",&n,&m,&s,&t);ll u,w,v;for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&u,&v,&w);add(u,v,w);add(v,u,0);//反边 }printf("%lld\n",getmaxflow());return 0;
}

EK算法

思路分析

EK是FF的优化：用bfs代替dfs，基于最短路思想以最快的方式找到增广路
bfs的缺点无法回溯则无法直接更新Gf
那么怎么更新Gf呢？
利用增广情况来更新 &Delta=flow[t]
u->v flow[v]=min(flow[u],e[i].cap) pre[v]=i

代码

#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll const M=520010;
ll const N=520010;
ll const INF=2005020600;
ll n,m,s,t;
ll cnt=1,head[N],vis[N];
struct edge{ll to,next,cap;
}e[M];
void add(ll u,ll v,ll cap)
{cnt++;e[cnt].to=v;e[cnt].next=head[u];e[cnt].cap=cap;head[u]=cnt;
}
ll dfs(ll u,ll flow)
{if(u==t)return flow;vis[u]=1;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(e[i].cap<=0||vis[v])continue;ll delta=dfs(v,min(e[i].cap,flow));if(delta<=0)continue;e[i].cap-=delta;e[i^1].cap+=delta;return delta;}return 0;
}
ll getmaxflow()
{ll maxflow=0,delta;while(delta=dfs(s,INF)) {memset(vis,0,sizeof(vis));maxflow+=delta;}return maxflow;
}
int main()
{scanf("%lld%lld%lld%lld",&n,&m,&s,&t);ll u,w,v;for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&u,&v,&w);add(u,v,w);add(v,u,0);//反边 }printf("%lld\n",getmaxflow());return 0;
}

Dinic算法

思路分析

Dinic是EK的优化，用bfs优化dfs的搜索效率，用dfs实现多路增广
添加dis[u]表示s到u的最短距离，用bfs找最短路对网络进行分层
则u->v的条件为 dis[u]+1=dis[v]&&e[i].cap>=0
两个优化
①当前弧优化：cur[u]相当于head[u]
②一个结论：bfs分层时只要找到第一个连到t的边就可以停止分层

代码

#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll const M=520010;
ll const N=520010;
ll const INF=2005020600;
ll n,m,s,t;
ll cnt=1,head[N],cur[N],dis[N];
struct edge{ll to,next,cap;
}e[M];
void add(ll u,ll v,ll cap)
{cnt++;e[cnt].to=v;e[cnt].next=head[u];e[cnt].cap=cap;head[u]=cnt;
}
bool bfs()
{memset(dis,0,sizeof(dis));queue<ll> q;q.push(s);dis[s]=1;while(q.size()){ll u=q.front();q.pop();for(ll i=head[u];i;i=e[i].next){ll v=e[i].to;if(dis[v]||e[i].cap<=0)continue;q.push(v);dis[v]=dis[u]+1;if(v==t)return 1;}}	return dis[t]!=0;
}
ll dfs(ll u,ll flow)
{if(u==t)return flow;for(int i=cur[u];i;i=e[i].next){cur[u]=i;int v=e[i].to;if(e[i].cap<=0||dis[u]+1!=dis[v])continue;ll delta=dfs(v,min(e[i].cap,flow));if(delta<=0)continue;e[i].cap-=delta;e[i^1].cap+=delta;return delta;}return 0;
}
ll getmaxflow()
{ll maxflow=0,delta;while(bfs()){for(int i=0;i<=n;i++)cur[i]=head[i];while(delta=dfs(s,INF)) maxflow+=delta;}return maxflow;
}
int main()
{scanf("%lld%lld%lld%lld",&n,&m,&s,&t);ll u,w,v;for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&u,&v,&w);add(u,v,w);add(v,u,0);//反边 }printf("%lld\n",getmaxflow());return 0;
}

ISAP算法

思路分析

ISAP是Dinic的优化，用bfs初始化最短路分层，用dfs更新最短路+实现多路增广
dis[u]表示u到t的最短距离
gap[x]表示u到t的最短距离为x的点的个数，出现gap[k]=0出现断层就结束

代码

#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll const M=520010;
ll const N=520010;
ll const INF=2005020600;
ll n,m,s,t;
ll cnt=1,head[N],cur[N],dis[N],gap[N];
struct edge{ll to,next,cap;
}e[M];
void add(ll u,ll v,ll cap)
{cnt++;e[cnt].to=v;e[cnt].next=head[u];e[cnt].cap=cap;head[u]=cnt;
}
void bfs()
{memset(dis,0,sizeof(dis));queue<ll> q;q.push(t);dis[t]=gap[1]=1;while(q.size()){ll u=q.front();q.pop();for(ll i=head[u];i;i=e[i].next){ll v=e[i].to;if(dis[v])continue;q.push(v);dis[v]=dis[u]+1;++gap[dis[v]];}}	
}
ll dfs(ll u,ll flow)
{if(u==t)return flow;ll delta=0;for(int i=cur[u];i;i=e[i].next){cur[u]=i;ll v=e[i].to;if(e[i].cap<=0||dis[u]!=dis[v]+1)continue;ll tmp=dfs(v,min(e[i].cap,flow-delta));if(tmp<=0)continue;e[i].cap-=tmp;e[i^1].cap+=tmp;delta+=tmp;if(delta==flow)return delta;}if(--gap[dis[u]]==0)dis[s]=n+1;++gap[++dis[u]];cur[u]=head[u];return delta;
}
ll getmaxflow()
{ll maxflow=0;bfs();for(int i=0;i<=n;i++)cur[i]=head[i];while(dis[s]<=n)maxflow+=dfs(s,INF);return maxflow;
}
int main()
{scanf("%lld%lld%lld%lld",&n,&m,&s,&t);ll u,w,v;for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&u,&v,&w);add(u,v,w);add(v,u,0);//反边 }printf("%lld\n",getmaxflow());return 0;
}

网络流之最大流（入门）【FF+EK+Dinic+ISAP】

目录

参考视频链接

基础知识

FF算法

EK算法

Dinic算法

ISAP算法