最大流——Dinic算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

前面花了很长时间弄明白了压入-重标记的各种方法，结果号称是O(V³)的算法测demo的时候居然TLE了一个点，看了题解发现所有人都是用Dinic算法写的，但它的复杂度O(V²E)明显高于前者，具体是怎么回事我也不太清楚。。。但是Dinic算法相对来说要好理解多了。

经过证明（然而并不知道怎么证明），在残余网络中增广路中的最短路，一定是对答案贡献最大的（即对求解时间贡献最大）增广路。

算法显而易见了，每次找增广路之前先bfs一遍得出残余网络中源点到每个点的最短路径（每条边长度固定为1），得到一张“层次图”，根据层次图来找最优增广路（每个点只能向等级恰好比它多1的点流）

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<map>
#include<queue>
#include<algorithm>
#include<ctime>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
inline int read(){
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<=''){
x=x*+ch-'';
ch=getchar();
}
return x;
}
const int MAXN=,MAXM=;
int to[MAXM],next[MAXM],value[MAXM];
int level[MAXN],cnt=,head[MAXN],s,t;
void _insert(int u,int v,int w){//链式前向星存图
to[cnt]=v;
value[cnt]=w;
next[cnt]=head[u];
head[u]=cnt++;
to[cnt]=u;
value[cnt]=;
next[cnt]=head[v];
head[v]=cnt++;
}
bool bfs(){//构建层次图
memset(level,,sizeof(level));
level[s]=;//level[i]表示每个点的层次，即源点到其的最短路径，初始化源点的层次为1（这个无所谓，只要层次递增即可）
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-;i=next[i]){
if(!level[to[i]]&&value[i]){
level[to[i]]=level[u]+;
q.push(to[i]);
}
}
}
return level[t];//如果没有得出汇点的层次图，说明不存在增广路
}
int dfs(int u,int f){//u为当前节点，f为当前节点残余流量
if(!f||u==t)return f;
int rest=;
for(int i=head[u];i!=-;i=next[i]){
if(value[i]&&level[u]+==level[to[i]]){//只能向层次恰好多1的点流入
int p=dfs(to[i],min(f,value[i]));//深搜寻找瓶颈
rest+=p;
f-=p;
value[i]-=p;
value[i^]+=p;
}
}
return rest;
}
int main(){
int n=read(),m=read();
s=read();t=read();
memset(head,-,sizeof(head));
rep(i,,m){
int u=read(),v=read(),w=read();
_insert(u,v,w);
}
int ans=;
while(bfs())ans+=dfs(s,INT_MAX);
cout<<ans<<endl;
return ;
}