2022.02.24 网络流复习

2022/4/15 23:17:37

编程Tag： Dep int 流量 head sizeof memset 复习 24 2022.02

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

2022.02.24 网络流复习

1. 有上下界网络流

1. 无源汇有上下界可行流

https://blog.csdn.net/wu_tongtong/article/details/73320968

1.1 建图

无源汇有上下界可行流(也就是循环流)
模型:一个网络,求出一个流,使得每条边的流量必须>=Li且<=Hi, 每个点必须满足总流入量=总流出量(流量守恒)(这个流的特点是循环往复,无始无终)
可行流算法的核心是将一个不满足流量守恒的初始流调整成满足流量守恒的流
流量守恒,即每个点的总流入量=总流出量
如果存在一个可行流,那么一定满足每条边的流量都大于等于流量的下限 因此我们可以令每条边的流量等于流量下限,得到一个初始流,然后建出这个流的残量网络 (即:每条边的流量等于这条边的流量上限与流量下限之差) 这个初始流不一定满足流量守恒,因此最终的可行流一定是在这个初始流的基础上增大了一些边的流量使得所有点满足流量守恒
因此我们考虑在残量网络上求出一个另不满足流量守恒的附加流, 使得这个附加流和我们的初始流合并之后满足流量守恒
那么首先我们需要开一个数组A,A[i]表示i在初始流中的流入量-流出量的值 那么A[i]的正负表示流入量和流出量的大小关系,
A[i]>0,说明附加流的流入量要小于流出量
A[i]<0,说明附加流的流入量要大于流出量
所以A[i]=附加流流出量-流入量
下面就用A[i]表示初始流中i的流入量-流出量
但是dinic算法能够求的是满足流量守恒的有源汇最大流, 不能在原网络上直接求一个这样的无源汇且不满足流量守恒的附加流 注意到附加流是在原网络上不满足流量守恒的,这启发我们添加一些原网络之外的边和点, 用这些边和点实现“原网络上流量不守恒”的限制
具体地,如果一个点i在原网络上的附加流中需要满足流入量>流出量(A[i]<0), 那么我们需要给多的流入量找一个去处,因此我们建一条从i出发流量=|A[i]|的边
如果A[i]>0,也就是我们需要让附加流中的流出量>流入量,我们需要让多的流出量有一个来路, 因此我们建一条指向i的流量=|A[i]|的边.
当然,我们所新建的从i出发的边也要有个去处,指向i的边也要有个来路, 因此我们新建一个虚拟源点ss和一个虚拟汇点tt (双写字母是为了和有源汇网络流中的源点s汇点t相区分) 新建的指向i的边都从ss出发,从i出发的边都指向tt 一个点要么有一条边指向tt,要么有一条边来自ss,
指向tt的边的总流量上限一定等于ss流出的边的总流量上限
因为每一条边对两个点的A[i]贡献一正一负大小相等,所以全部点的A[i]之和等于0, 即小于0的A[i]之和的绝对值=大于0的A[i]之和的绝对值.
如果我们能找到一个流满足新加的边都满流,这个流在原图上的部分就是我们需要的附加流
那么怎样找出一个新加的边都满流的流呢? 可以发现假如存在这样的方案,这样的流一定是我们所建出的图的ss-tt最大流, 所以跑ss到tt的最大流即可

第一步，令每条边流量为流量下限，建出这个图的残量网络，每条边的流量=流量上限-流量下限；

第二步，求出原图不满足流量守恒的附加流，附加流与原图合并后流量守恒。设\(A_i\)表示原图中流入流量-流出流量，那么对于现在的图来说：

  1. \(A_i>0\)，附加流流入流量小于流出流量；
  2. \(A_i<0\)，附加流流入流量大于流出流量；

简而言之，\(A_i\)=附加流流出流量-流入流量。

第三步，对于没有来源或者去处的流量，我们建一个全新的源点Si和全新的汇点Ti来为这些流量提供一个温暖的家：

  1. 对于\(A_i>0\)，从Si到i建一条容量为\(|A_i|\)的边；
  2. 对于\(A_i<0\)，从i到Ti建一条容量为\(|A_i|\)的边。

然后从Si到Ti跑Dinic或Ek（菜菜的eleveni其他算法学得并不好，只有Dinic与Ek学得十分熟练）。

1.2 对于1.1的一些说明

1.2.1 指向Ti的流量上限之和=从Si流出的流量上限之和

一条边对于起点和终点流量的影响是大小相等，正负相反的，所以整个图的\(A_i\)之和为0.

1.2.2 为什么跑最大流

因为如果想要求到想要的附加流，第三步中建的边必须满流（废话，要不然空穴来网络流？必须先把缺失的流量补全才能继续在上面进行骚操作），那么就跑最大流。

如果最大流不等于流出Si的流量之和，说明这个图没有可行流，孩纸，洗洗睡吧；

如果最大流等于流出Si的流量之和，说明已经找到了可行流，每条边可行流流量=原图中的流量下限+附加流中的流量（跑完Dinic后，新图中反向边的权值），换而言之就是新图与原图合起来流量平衡，现在新图正向边流量平衡，说明新图反向边与原图流量平衡；

如果最大流大于……没有大于，要不然就又是空穴来流量了！

2. 有源汇有上下界可行流

https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-p5192

2.1 有源汇有上下界可行流

既然咱会无源汇有上下界可行流，那就可以把有源汇有上下界可行流变成无源汇有上下界可行流。

最简单的方法是：从T到S连一条容量为inf的边，让流量循环一下，这就不平衡了。

接下来跑无源汇有上下界可行流模板就好了。

2.2 有源汇有上下界最大流

咱根据有源汇有上下界可行流的想法，先跑出来可行流flow1，此时在新图上已经找不出来从Si到Ti增广路了，但是在原图中从S到T可能会存在增广路。

所以我们要删掉从T到S容量为inf的边，不然永远都是一个循环，跑不出去。然后继续跑从S到T的Dinic，得出旧图上的最大流为flow2，总的最大流就是flow1+flow2。

2.3 有源汇有上下界最小流

老规矩，先算出从Si到Ti的最大流flow1。

根据有源汇有上下界最大流的想法，咱可以先删去从T到S容量为inf的边，然后从T到S跑一个最大流，算出需要退回去的最大流量为flow2，说明从S到T剩下的最小流就是flow1-flow2。

3. 练习题

PS：洛谷上只有三道题，所以有些题来自ZOJ，这些题会在题号前面加上“ZOJ”这三个字符。

3.1 ZOJ2314 Reactor Cooling（无源汇有上下界网络流模板）

https://zoj.pintia.cn/problem-sets/91827364500/problems/91827365813

没啥可说的，毕竟是模板。非要说啥，那就是visual记得清零！

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
const int M=1e5+10;
int n,m,cnt=1,preflow[N],stain[N],head[N],dep[N],cur[N],visual;
int S,T,id[N],Ttot;
struct node{
	int to,next,val;
}a[M];

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar(); 
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
inline void addi(int u,int v,int w){
	++cnt;
	a[cnt].to=v;
	a[cnt].val=w;
	a[cnt].next=head[u];
	head[u]=cnt;
}
inline void add(int u,int v,int w){
	addi(u,v,w);addi(v,u,0);
}
inline int bfs(int s,int t){
	memset(dep,0,sizeof(dep));
	memcpy(cur,head,sizeof(head));
	queue<int>q;
	dep[s]=1;q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=a[i].next){
			int v=a[i].to;
			if(a[i].val&&!dep[v])dep[v]=dep[x]+1,q.push(v);
		}
	}
	return dep[t];
}
inline int dfs(int x,int t,int f){
	if(t==x)return f;
	int ans=0,fi=0;
	for(int i=cur[x];i&&f>ans;i=a[i].next){
		int v=a[i].to;cur[x]=i;
		if(a[i].val&&dep[v]==dep[x]+1&&(fi=dfs(v,t,min(f-ans,a[i].val)))>0)
		a[i].val-=fi,a[i^1].val+=fi,ans+=fi;
	}
	return ans;
}
inline int Dinic(int s,int t){
	int flow=0;
	while(bfs(s,t)){
		int x=0;
		if((x=dfs(s,t,1<<30))>0)flow+=x;
	}
	return flow;
}
inline bool check(){
	for(int i=head[S];i;i=a[i].next)if(a[i].val)return false;
	return true;
}

signed main(){
	cin>>Ttot;
	while(Ttot--){
		memset(stain,0,sizeof(stain));
		memset(preflow,0,sizeof(preflow));
		memset(head,0,sizeof(head));
		memset(a,0,sizeof(a));
		memset(id,0,sizeof(id));
		cnt=1;visual=0;
		cin>>n>>m;
		S=n+1,T=S+1;
		for(int i=1;i<=m;i++){
			int u,v,w,x;
			u=read();v=read();w=read();x=read();
			preflow[i]=w;
			stain[u]-=w;stain[v]+=w;
			add(u,v,x-w);
			id[i]=cnt;
		}
		for(int i=1;i<=n;i++)
		if(stain[i]>0)add(S,i,stain[i]),visual+=stain[i];
		else if(stain[i]<0)add(i,T,-stain[i]);
		int flow=Dinic(S,T);
		if(flow==visual){
			puts("YES");
			for(int i=1;i<=m;i++)cout<<preflow[i]+a[id[i]].val<<endl;
		}else puts("NO");
	}
	return 0;
}

3.2 P5192 Zoj3229 Shoot the Bullet|东方文花帖|（有源汇有上下界最大流模板）

https://www.luogu.com.cn/problem/P5192

温馨提示：不要尝试作死，比如想试试不删掉从T到S容量为inf的边会发生什么，有的时候，你机房的电脑可能会抗议！

洛谷：只需要输出总照片数

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;

const int N=2e3+10;
const int M=1e6+10;
const int maxn=1e7;
int n,m,cnt=1,preflow[M],stain[N],head[N],dep[N],cur[N],visual;
int S,T,Si,Ti,id[400][1010],girl[1010],fin[400][1010];
struct node{
	int to,next,val;
}a[M];

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar(); 
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
inline void addi(int u,int v,int w){
	++cnt;
	a[cnt].to=v;
	a[cnt].val=w;
	a[cnt].next=head[u];
	head[u]=cnt;
}
inline void add(int u,int v,int w){
	addi(u,v,w);addi(v,u,0);
}
inline int bfs(int s,int t){
	memset(dep,0,sizeof(dep));
	memcpy(cur,head,sizeof(head));
	queue<int>q;
	dep[s]=1;q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=a[i].next){
			int v=a[i].to;
			if(a[i].val&&!dep[v])dep[v]=dep[x]+1,q.push(v);
		}
	}
	return dep[t];
}
inline int dfs(int x,int t,int f){
	if(t==x)return f;
	int ans=0,fi=0;
	for(int i=cur[x];i&&f>ans;i=a[i].next){
		int v=a[i].to;cur[x]=i;
		if(a[i].val&&dep[v]==dep[x]+1&&(fi=dfs(v,t,min(f-ans,a[i].val)))>0)
		a[i].val-=fi,a[i^1].val+=fi,ans+=fi;
	}
	return ans;
}
inline int Dinic(int s,int t){
	int flow=0;
	while(bfs(s,t)){
		int x=0;
		if((x=dfs(s,t,1<<30))>0)flow+=x;
	}
	return flow;
}

signed main(){
	while(~scanf("%d%d",&n,&m)){
		memset(head,0,sizeof(head));
		memset(a,0,sizeof(a));
		memset(id,0,sizeof(id));
		memset(stain,0,sizeof(stain));
		memset(girl,0,sizeof(girl));
		memset(preflow,0,sizeof(preflow));
		visual=0,cnt=1;
		S=n+m+1,T=S+1;Si=T+1,Ti=Si+1;
		for(int i=1;i<=m;i++){
			girl[i]=read();
			stain[T]+=girl[i];stain[n+i]-=girl[i];
			add(n+i,T,maxn-girl[i]);//old graph
		}
		for(int i=1;i<=n;i++){
			int C,D;
			C=read();D=read();
			id[i][0]=C;
			add(S,i,D);//old graph
			for(int j=1;j<=C;j++){
				int u,v,w;
				u=read();v=read();w=read();
				++u;
				stain[n+u]+=v;stain[i]-=v;
				add(i,n+u,w-v);//new graph and old graph
				id[i][j]=u;
			}
		}
		for(int i=1;i<=n+m+2;i++)
		if(stain[i]>0)add(Si,i,stain[i]),visual+=stain[i];
		else if(stain[i]<0)add(i,Ti,-stain[i]);
		add(T,S,maxn);
		//cout<<"first dinic "<<endl;
		int flow=Dinic(Si,Ti);
		//cout<<flow<<endl;
		if(flow!=visual)puts("-1\n");
		else{
			a[cnt].val=0;a[cnt^1].val=0;
			flow+=Dinic(S,T);
			for(int i=1;i<=n;i++)
			for(int j=head[i];j;j=a[j].next)if(j%2==0){
				int v=a[j].to;
				fin[i][v-n]=a[j^1].val;
			}
			cout<<flow<<endl<<endl;
			/*for(int i=1;i<=n;i++){
				for(int j=1;j<=id[i][0];j++)
				cout<<fin[i][id[i][j]]<<endl;
			}*/
		}
	}
	return 0;
}

ZOJ：输出每天每个姑娘的照片数的时候记得加上流量下届！

为什么这两个代码长得差不多呢？因为我原本想直接写ZOJ这道题，结果没加上流量下届，写挂了，于是直接先交了洛谷的，拐回来继续修ZOJ的。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;

const int N=2e3+10;
const int M=1e6+10;
const int maxn=1e7;
int n,m,cnt=1,preflow[M],stain[N],head[N],dep[N],cur[N],visual;
int S,T,Si,Ti,id[400][1010],girl[1010],fin[400][1010],low[400][1010];
struct node{
	int to,next,val;
}a[M<<1];

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar(); 
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
inline void addi(int u,int v,int w){
	++cnt;
	a[cnt].to=v;
	a[cnt].val=w;
	a[cnt].next=head[u];
	head[u]=cnt;
}
inline void add(int u,int v,int w){
	addi(u,v,w);addi(v,u,0);
}
inline int bfs(int s,int t){
	memset(dep,0,sizeof(dep));
	memcpy(cur,head,sizeof(head));
	queue<int>q;
	dep[s]=1;q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=a[i].next){
			int v=a[i].to;
			if(a[i].val&&!dep[v])dep[v]=dep[x]+1,q.push(v);
		}
	}
	return dep[t];
}
inline int dfs(int x,int t,int f){
	if(t==x)return f;
	int ans=0,fi=0;
	for(int i=cur[x];i&&f>ans;i=a[i].next){
		int v=a[i].to;cur[x]=i;
		if(a[i].val&&dep[v]==dep[x]+1&&(fi=dfs(v,t,min(f-ans,a[i].val)))>0)
		a[i].val-=fi,a[i^1].val+=fi,ans+=fi;
	}
	return ans;
}
inline int Dinic(int s,int t){
	int flow=0;
	while(bfs(s,t)){
		int x=0;
		if((x=dfs(s,t,1<<30))>0)flow+=x;
	}
	return flow;
}

signed main(){
	while(~scanf("%d%d",&n,&m)){
		memset(head,0,sizeof(head));
		memset(a,0,sizeof(a));
		memset(id,0,sizeof(id));
		memset(stain,0,sizeof(stain));
		memset(girl,0,sizeof(girl));
		memset(preflow,0,sizeof(preflow));
		memset(low,0,sizeof(low));
		memset(fin,0,sizeof(fin));
		visual=0,cnt=1;
		S=n+m+1,T=S+1;Si=T+1,Ti=Si+1;
		for(int i=1;i<=m;i++){
			girl[i]=read();
			stain[T]+=girl[i];stain[n+i]-=girl[i];
			add(n+i,T,maxn-girl[i]);//old graph
		}
		for(int i=1;i<=n;i++){
			int C,D;
			C=read();D=read();
			id[i][0]=C;
			add(S,i,D);//old graph
			for(int j=1;j<=C;j++){
				int u,v,w;
				u=read();v=read();w=read();
				++u;
				//fin[i][j]=v;
				stain[n+u]+=v;stain[i]-=v;
				add(i,n+u,w-v);//new graph and old graph
				id[i][j]=u;
				low[i][j]=v;
			}
		}
		for(int i=1;i<=n+m+2;i++)
		if(stain[i]>0)add(Si,i,stain[i]),visual+=stain[i];
		else if(stain[i]<0)add(i,Ti,-stain[i]);
		add(T,S,maxn);
		//cout<<"first dinic "<<endl;
		int flow=Dinic(Si,Ti);
		//cout<<flow<<endl;
		if(flow!=visual)puts("-1\n");
		else{
			a[cnt].val=0;a[cnt^1].val=0;
			flow+=Dinic(S,T);
			for(int i=1;i<=n;i++)
			for(int j=head[i];j;j=a[j].next)if(j%2==0){
				int v=a[j].to;
				fin[i][v-n]+=a[j^1].val;
				//cout<<"i "<<i<<" j "<<v-n<<" flow "<<fin[i][v-n]<<endl;
			}
			cout<<flow<<endl;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=id[i][0];j++)
				cout<<fin[i][id[i][j]]+low[i][j]<<endl;
			}
			cout<<endl;
		}
	}
	return 0;
}


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


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程