例题:
题意:如题，给出一个网络图，以及其源点和汇点，求出其网络最大流.(n<=10000,m<=100000).
EK增广路算法:不断用(BFS)寻找增广路(找到一条从(S)到(T)的路径,同时计算出路径上各边的剩余容量的最小值(minn),则网络的流量就可以增加(minn)),直至网络上不存在增广路为止.
时间复杂度(n^2m^2),实际运用中更快.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=10005;
const int M=200005;
int n,m,s,t,max_flow;
int visit[N],minn[N],pre[N];
int tot,head[N],nxt[M],to[M],w[M];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
inline bool bfs(){
memset(visit,0,sizeof(visit));
queue<int>q;q.push(s);visit[s]=1;
minn[s]=1e9;//增广路路各边的最小剩余容量
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=nxt[i]){
if(w[i]){//如果还剩余容量
int v=to[i];if(visit[v])continue;
minn[v]=min(minn[u],w[i]);//更新
pre[v]=i;//记录从哪条边转移过来的
q.push(v);visit[v]=1;
if(v==t)return 1;//走到了汇点,表示找到了一条从s到t的增广路
}
}
}
return 0;
}
inline void update(){
int x=t;
while(x!=s){//根据pre往前找
int i=pre[x];
w[i]-=minn[t];//正向边减这次的流量
w[i^1]+=minn[t];//反向边加这次的流量
x=to[i^1];
}
max_flow+=minn[t];//更新答案
}
int main(){
n=read();m=read();s=read();t=read();
tot=1;//建图技巧
for(int i=1;i<=m;++i){
int a=read(),b=read(),c=read();
add(a,b,c);add(b,a,0);//注意反向边边权为0
}
while(bfs())update();//不断增广
printf("%d
",max_flow);
return 0;
}
(Dinic)算法:
1.在残量网络上(BFS)求出节点的层次,构造分层图
2.在分层图上(DFS)寻找增广路,在回溯时实时更新剩余容量.另外,每个点可以流向多条出边.
3.不断重复上述步骤,直到在残量网络中(S)不能到达(T).
时间复杂度(n^2m),实际运用中更快.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=10005;
const int M=200005;
int n,m,s,t,max_flow;
int dep[N];
int tot,head[N],nxt[M],to[M],w[M];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
inline bool bfs(){//分层,dep即层数
memset(dep,0,sizeof(dep));
queue<int>q;q.push(s);dep[s]=1;
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(w[i]&&!dep[v]){
q.push(v);dep[v]=dep[u]+1;
if(v==t)return 1;//分层完毕就退出
}
}
}
return 0;
}
inline int dinic(int u,int flow){//增广路
if(u==t)return flow;
int rest=flow;
for(int i=head[u];i&&rest;i=nxt[i]){
int v=to[i];
if(w[i]&&dep[v]==dep[u]+1){
int k=dinic(v,min(rest,w[i]));
if(!k)dep[v]=0;
w[i]-=k;
w[i^1]+=k;
rest-=k;
}
}
return flow-rest;
}
int main(){
n=read();m=read();s=read();t=read();
tot=1;
for(int i=1;i<=m;++i){
int a=read(),b=read(),c=read();
add(a,b,c);add(b,a,0);
}
int flow=0,inf=1e9;
while(bfs())
while(flow=dinic(s,inf))max_flow+=flow;
printf("%d
",max_flow);
return 0;
}