重修 网络最大流(即最小割)

本蒟蒻只讲一些我常常出错的部分,具体还要靠 OI-wiki:Dinic 的帮助。

啥是最大流?

相当于有一个供水站,一个用户,中间有复杂的水管(每一根单向且有单位时间传输量限制)网络,求用户单位时间内获得的最大水量。

Dinic 咋弄?

每次先 BFS 按照离原点 \(S\) 的距离将图分层,再在分层图上 DFS,终止条件为 BFS 时候汇点 \(T\) 与 \(S\) 不连通。DFS 时每次找一条通的管道注水,当然一次 DFS 整体看起来像打通了一棵树(多路增广)。

如果一条边已经被增广过,那么它就没有可能被增广第二次。那么,我们下一次进行增广的时候,就可以不必再走那些已经被增广过的边(当前弧优化)。

时间?

\(O(n^2m)\)(前提是加上多路增广和当前弧优化)(事实上在一般的网络上,Dinic 算法往往达不到这个上界。)

特别地,在求解二分图最大匹配问题时,Dinic 算法的时间复杂度是 \(O(m\sqrt{n})\)。

建议?

建议一遍写对,难调的很 qwq。

我的代码?

Luogu 模板题:

//Said no more counting dollars. We'll be counting stars.
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define int long long
#define N 210
#define M 5010
const int inf=1e14;
int n,m,s,t;
struct node{int to,nxt,res;}e[2*M];//res:残量 有反向边,空间开两倍 
int head[N],cur[N],tot=1;//cur:当前到的前向星(当前弧优化) tot=1:方便 xor 1 取反向边 
inline void adde(int x,int y,int z){
	e[++tot]={y,head[x],z}; head[x]=tot;
	e[++tot]={x,head[y],0}; head[y]=tot;//反向边 init 0 
}
queue<int> q;
int dep[N];//分层 
bool bfs(){
	For(i,1,n) dep[i]=0;//分层图 
	dep[s]=1;
	while(!q.empty()) q.pop();
	q.push(s);
	int x;
	while(!q.empty()){
		x=q.front();
		q.pop();
		cur[x]=head[x];//init 当前到的前向星
		for(int i=head[x],to;i;i=e[i].nxt){
			to=e[i].to;
			if(!e[i].res || dep[to]) continue;
			dep[to]=dep[x]+1;
			q.push(to);
		} 
	}
	return dep[t];//返回是否连通 
}
int dfs(int x,int flow){
	if(x==t) return flow;//送达
	int ans=0,tmp,to;
	for(int& i=cur[x];i;i=e[i].nxt){//传实参,cur[x]随之改变 
		to=e[i].to;
		if(!e[i].res || dep[to]!=dep[x]+1) continue; //要有空间增广 & 要按照分层图增广 
		tmp=dfs(to,min(flow,e[i].res));
		e[i].res-=tmp;
		e[i^1].res+=tmp;
		ans+=tmp;
		flow-=tmp;
		if(!flow) break;//已经结束咧! 
	} 
	return ans;
}
signed main(){IOS;
	cin>>n>>m>>s>>t;
	int x,y,z;
	while(m--){
		cin>>x>>y>>z;
		adde(x,y,z);
	} 
	int ans=0;
	while(bfs()) ans+=dfs(s,inf);
	cout<<ans<<endl;
return 0;}

最小点割(要拆点)原题

//Said no more counting dollars. We'll be counting stars.
#pragma GCC optimize(2,3)//For Web Contests
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb emplace_back
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define int long long
#define N 220
#define endl '\n'
const int inf=1e12;
struct node{int to,c,nxt;}e[N*N];
int head[N],cur[N],tot=1,n,m,s,t,dep[N],col[N];
inline void adde(int x,int y,int c){
	e[++tot]={y,c,head[x]};head[x]=tot;
	e[++tot]={x,0,head[y]};head[y]=tot;
}
queue<int> q;
bool bfs(){
	For(i,1,2*n+2) dep[i]=0;
	dep[s]=1;
	while(!q.empty()) q.pop();
	q.push(s);
	int x;
	while(!q.empty()){
		x=q.front();
		cur[x]=head[x];
		q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			if(!e[i].c || dep[e[i].to]) continue;
			dep[e[i].to]=dep[x]+1;
			q.push(e[i].to);
		}
	}
	return dep[t];
}
int dfs(int rt,int flow){
	if(rt==t) return flow;
	int res=0,tmp;
	for(int &i=cur[rt];i;i=e[i].nxt){//当前弧优化&多路增广 
		if(!e[i].c || dep[e[i].to]!=1+dep[rt]) continue;
		tmp=dfs(e[i].to,min(flow,e[i].c));
		e[i].c-=tmp;
		e[i^1].c+=tmp;
		flow-=tmp;
		res+=tmp;
		if(!flow) break;
	}
	return res;
}
int dinic(){
	int res=0;
	while(bfs()) res+=dfs(s,inf);
	return res;
}
void color(int rt){
	col[rt]=1;
	for(int i=head[rt];i;i=e[i].nxt){
		if(!e[i].c || col[e[i].to]) continue;
		color(e[i].to);
	}
}
signed main(){IOS;
	cin>>n>>m;
	int x,y;
	while(m--){
		cin>>x>>y;
		adde(x,y+n,inf);
		adde(y,x+n,inf);
	} 
	For(i,1,n){
		cin>>x;
		if(i==1 || i==n) x=inf;
		adde(i+n,i,x);
	}
	s=n*2+1,t=n*2+2;
	adde(s,1,inf);
	adde(n*2,t,inf);
	cout<<dinic()<<endl;
	color(s);
	vector<int> ans;
	For(i,2,n-1)
		if(col[i]!=col[i+n])
			ans.pb(i);
	cout<<ans.size()<<endl;
	for(int i:ans) cout<<i<<" "; cout<<endl;
return 0;}
上一篇:记一次redis异常MISCONF Redis is configured to save RDB snapshots, but is currently not able


下一篇:XDOJ34