网络流略解
网络流
洛谷博客 github vercel
定义
用水管来类比：
自来水厂（源点）要经过水管（边）把水运到石老板家（汇点）
每条单向水管连接两个站点，水管都有一个最大流量，源点有无限的水。显然，每条水管可能有水流，可能没有
问：自来水厂最多能给石老板送多少水
重点概念：
- 网络：图（一般为有向无重边）
- 容量网络：边权为该边容量的网络
- 流量网络：边权为该边实际流量的网络
- 剩余网络：容量网络边权减去剩余网络对应边权形成的网络
- 满流：流量网络的流量达到最大（即流入汇点的流量最大）
- 增广路：剩余网络中从源到汇使路径中最小剩余边权不为零的路径
- 超级源 & 超级汇：有多个源点与汇点时，建立一个超级源和一个超级汇，连向源点和汇点。
性质：
- 剩余网络在满流时不会有一条增广路
若满流时剩余网络仍有增广路，则沿着增广路增加流量总能使最终流量增加
- 任何一个合法的流量网络中，除了源和汇外的所有节点，入度都等于出度
水不会在中间节点凭空产生或消失
最大流最小割
给定一张图
割集
即
最小割：边权和最小的割集
即花费最小代价把源点到汇点的所有路径切断，使源点汇点不连通，切断一条边的代价为它的边权。
举一个形象的例子：
某恐怖分母分子要花费最小代价切断若干条水管，使石老板家用不了自来水
可怜的石老板
性质：
- 一个流量网络的每一个割集，对应的流量和都等于总流量
一个形象的例子：恐怖分子切断了若干水管，使原来流向石老板家的水全部流走，最终从被切断水管流出的水量就是原来流向石老板家的水
- 同一张图上，每一个割都大于等于每一个流
考虑任意一个割集和任意一个流，由上一条性质得，割集对应的流量等于总流量，而割集对应的边权和大于等于边权对应流量（每一条边的流量小于等于边权）
- 最大流等于最小割
满流时，根据增广路的性质，剩余网络中源点汇点不存在最小剩余边权不为零的路径。断开所有剩余流量为零的边，另
S 为所有与源点连通的点集，T=V-S ，则割集C(S,T) 包含的所有边剩余流量为0，即流量等于容量。由此得C(S,T) 的边权和为最大流的流量。由上一条性质得，C(S,T) 为最小割。综上，最大流等于最小割。
求最大流
部分引自 OI-Wiki
这里仅介绍三种算法。
- Edmonds-Karp
- 预流推进
- 最高标号预流推进（最快）
Edmonds-Karp
每次 BFS 找到增广路，增广的同时把反向边边权增加即可。增广的时候要注意建造反向边，原因是这条路不一定是最优的，这样子程序可以进行反悔。假如我们对这条路进行增广了，那么其中的每一条边的反向边的流量就是它的流量。
预流推进
预流推进的核心在于允许节点的流入大于流出。我们把允许流入大于流出的网络称为预流。
预流推进算法维护每个结点的高度
初始化时，
最高标号预流推进
在预流推进法的基础上用数据结构维护高度最高的节点，即为最高标号预流推进（HLPP）
HLPP 还可进行如下优化：
-
将
h(u) 初始化为dis(u,t) ，将h(s) 仍初始化为n 。用 BFS 求出dis(u,t) ，即可减少大量重贴标签操作。 -
用桶代替优先队列，复杂度降低一个
\log n 。 -
因为每次取出的是最高节点，而重贴标签又只会增加当前节点高度，所以如果当前节点高度上没有其他节点，比当前节点高的所有节点都不可能向当前节点以后的节点推送流量，所以为了尽快将流量推送回
s ，我们把所有比当前节点高的节点高度变为n+1 。
优化后时间复杂度为
放上本人20分钟写完的HLPP代码，部分参考 OI-Wiki 与 P4722 题解，因为本人巨喜欢空行，核心部分写了 65 行，一共 110 行。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
// stO OI-Wiki Orz
#define il inline
#define For(i,l,u) for(int i=(l);i<=(u);i++)
#define RFor(i,l,u) for(int i=(u);i>=(l);i--)
const int INF=2147483647;
using namespace std;
const int maxn=2405,maxm=120005;
int n,m,s,t;
namespace E{
int f[maxm*2],t[maxm*2],v[maxm*2],nxt[maxm*2],oth[maxm*2];
int tot,fst[maxn];
il int add(int u_,int v_,int w_){ // add edge
++tot;f[tot]=u_,t[tot]=v_,v[tot]=w_,nxt[tot]=fst[u_],fst[u_]=tot;return tot;
}
il void addf(int u,int v,int w){ // add edge and inverse edge
int d1=add(u,v,w),d2=add(v,u,0);
oth[d1]=d2;oth[d2]=d1;
}
}
#define ForP(u,i) for(int i=E::fst[u];i;i=E::nxt[i])
namespace Flow{
int h[maxn],e[maxn],vis[maxn],gap[maxn],mxh;
vector<int> mp[maxn];
il void bfs(int s){
static queue<int> q;
while(!q.empty()){ q.pop(); }
q.push(s);h[s]=0;vis[s]=1;
while(!q.empty()){
int u=q.front(),v;q.pop();
ForP(u,i){
if(!vis[v=E::t[i]] && E::v[E::oth[i]]){
vis[v]=1;h[v]=h[u]+1;q.push(v);
}
}
}
}
il int push(int u){
bool init=u==s; // good idea from OI-Wiki
ForP(u,i){
int v=E::t[i],w=E::v[i];
if(w==0 || ( !init && h[v]!=h[u]-1) ){ continue; }
int sw=init?w:min(w,e[u]); // from OI-Wiki too
if(e[v]==0 && v!=s && v!=t){ mp[h[v]].push_back(v);mxh=max(mxh,h[v]); }
e[u]-=sw;e[v]+=sw;E::v[i]-=sw;E::v[E::oth[i]]+=sw;
if(e[u]==0){ return 0; }
}
return e[u];
}
il void relabel(int u){
h[u]=INF;
ForP(u,i){ if(E::v[i]){ h[u]=min(h[u],h[E::t[i]]); } }
if(++h[u]<n){
mp[h[u]].push_back(u);mxh=max(mxh,h[u]);gap[h[u]]++;
}
}
il int sel(){
while(mp[mxh].size()==0 && mxh>=0){ mxh--; }
return mxh==-1?0:mp[mxh][mp[mxh].size()-1];
}
il int HLPP(){
For(i,1,n){ h[i]=INF; } bfs(t);
if(h[s]==INF){ return 0; }
For(i,1,n){ if(h[i]!=INF){gap[h[i]]++;} }
h[s]=n;push(s);
int u;
while(u=sel()){ // from OI-Wiki
mp[mxh].pop_back();
if(push(u)){
if((--gap[h[u]])==0){
For(i,1,n){
if(i!=s && i!=t && h[u]<h[i] && h[i]<n+1){
h[i]=n+1;
}
}
}
relabel(u);
}
}
return e[t];
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
E::addf(u,v,w);
}
printf("%d\n",Flow::HLPP());
return 0;
}应用
P4722 【模板】最大流 加强版 / 预流推进
这题卡 Dinic...当然一般题目都不会卡它
建议参考 网络流24题
这里放上一道偏模板的题:U189165
考察了讲到的绝大部分知识