网络流初步

本文主要是介绍网络流初步，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最大流&最小费用最大流

最大流（dinic算法）

求最大流的方法有FF,EK,dinic，dinic最优

dinic算法的核心是对图分层

定义一个节点的“层”\(dis_x\) 为\(x\)到源点\(s\)的距离。可以通过一遍bfs对图分好层

dinic算法规定：每次流水只能从第i层流向第i+1层，不能在同一层流，也不能回流。同时为了反悔，增加了反向边，通常把一组反向边的编号\(i,j\)设为2,3;4,5;6,7，从而可以由e异或1方便地得到它的反向边编号。每当流过一条边时，就把本边限流量-真实流量，反向边流量+真实流量

显然，只有流量为正的边才能流

当有一时刻发现源点汇点不再联通，就无法给图分层，于是算法结束

复杂度\(O(n^2m)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e15;
int n,m,s,t,p=1;
int cur[205],we[10005],dis[205];
queue<int>Q;
struct edge {
	int x,id;
};
vector<edge>G[205];
bool bfs(){
	memset(dis,0,sizeof(dis));
	while(!Q.empty())Q.pop();
	Q.push(s);dis[s]=1;
	while(!Q.empty()){
		int now=Q.front();Q.pop();
		for(int i=0;i<G[now].size();i++){
			int y=G[now][i].x,z=we[G[now][i].id];
			if(z&&!dis[y])Q.push(y),dis[y]=dis[now]+1;
		}
	}
	return dis[t];
}
int dfs(int x,int in){
	if(x==t)return in;
	int out=0;
	for(int i=0;i<G[x].size()&&in;i++){
		int y=G[x][i].x,z=we[G[x][i].id];
		if(z&&dis[y]==dis[x]+1){
			int los=dfs(y,min(in,z));
			we[G[x][i].id]-=los;
			we[G[x][i].id^1]+=los;
			in-=los;
			out+=los;
		}
	}
	if(!out)dis[x]=0;
	return out;
}
signed main()
{
	cin>>n>>m>>s>>t;
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		G[u].push_back((edge){v,++p});
		G[v].push_back((edge){u,++p});
		we[p^1]=w,we[p]=0;
	}
	int ans=0;
	while(bfs()){//cout<<ans<<endl;
		ans+=dfs(s,INF);
	}
	cout<<ans<<endl;
}

最小费用最大流（EK算法）

贪心，每次寻找s->t的费用最短路，路径上的所有边的流量最小值即为这一次的流量Min，那么这次所消耗的费用Min*(边的费用之和)

同样地，每次-Min后反向边+Min

进行若干次，直到图不连通（无法找到最短路）

最短路可以用dij/spfa

复杂度\(O(nm^2)\)（通常情况下不会达到）

//在这里加o2优化
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 5005
#define M 100005
using namespace std;
int n,m,s,t,p=1;
struct edge {
	int u,c,id;
};
vector<edge>G[N];
queue<int>Q;
int we[M],dis[N],inq[N];
void con(int u,int v,int w,int c,int p){
	G[u].push_back((edge){v,c,p});
	we[p]=w;
}
struct nodepre{
	int u,id,c;
}pre[N];
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;inq[s]=1;Q.push(s);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=0;
		for(int i=0;i<G[x].size();i++){
			int y=G[x][i].u,z=we[G[x][i].id],w=G[x][i].c;
			if(z&&dis[y]>dis[x]+w){
				dis[y]=dis[x]+w;
				pre[y].u=x,pre[y].id=G[x][i].id,pre[y].c=w;
				if(!inq[y])inq[y]=1,Q.push(y);
			}
		}
	}
	return dis[t]!=INF;
}
int main()
{
    ios::sync_with_stdio(false);
	cin>>n>>m;s=1,t=n;
	for(int i=1,u,v,w,c;i<=m;i++){
		cin>>u>>v>>w>>c;
		con(u,v,w,c,++p);
		con(v,u,0,-c,++p);
	}
	int flow=0,ans=0;
	while(spfa()){
		int Min=INF;
		for(int i=t;i!=s;i=pre[i].u)
			Min=min(Min,we[pre[i].id]);
		for(int i=t;i!=s;i=pre[i].u){
			we[pre[i].id]-=Min;
			we[pre[i].id^1]+=Min;
			ans+=pre[i].c*Min;
		}
		flow+=Min;
	}
	cout<<flow<<' '<<ans<<endl;
}

这篇关于网络流初步的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！