参考视频链接

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

1. 【网络流模型】基础知识篇
2. 【网络流模型】FF算法
3. 【网络流模型】EK算法
4. 【网络流模型】Dinic算法
5. 【网络流模型】ISAP算法

基础知识

1. 网络：具有一个出度为0的点s和一个入度为0的点t的有向图，每一条边上有权值
2. 源点：出度为0的点s
3. 汇点：入度为0的点t
4. 容量：边上的权值，用c(u,v)表示
   假设需要从s发货到t
5. 流量：实际运送的货物量
   ① 边上的流量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最大流（最多运送货物的总量）就是我们需要研究的问题
6. 割：一个边集cut，若删去该边集则s与t不连通
   |cut| max=所有边数 min最小割就是我们需要研究的问题
7. 费用流：保证在最大流的情况下考虑费用，最小费用最大流
8. 残量网络Gf : c’(u,v)=c(u,v)-f(u,v) 残留（量）
9. 增广路：从s到t能够增加运货量的路

---

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

FF算法

1. 思路分析

• 怎么求？
  在残量网络上不断找增广路，每次增广得到的增广量Δ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)

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算法

1. 思路分析

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

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;
}

Dinic算法

1. 思路分析

• 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的边就可以停止分层

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],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算法

1. 思路分析

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

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],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;
}