首页 > 其他分享 >【学习笔记】网络流各种形式及模型

【学习笔记】网络流各种形式及模型

时间:2023-08-21 16:45:19浏览次数:40  
标签:int res 模型 网络 笔记 add tot lev delta

各种形式

普通网络流

Dinic

#include<bits/stdc++.h>
using namespace std;
int n,tot=1,first[210],nnext[10010],to[10010],w[10010],que[210],src,des,lev[210],cur[210];
void add(int x,int y,int z){
	nnext[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
int bfs(){
	int q=1,u;
	memset(que,0,sizeof(que));
	for(int i=1;i<=n;i++){
		lev[i]=-1;
		cur[i]=first[i];
	}
	que[1]=src;
	lev[src]=0;
	for(int l=1;l<=q;l++){
		u=que[l];
		for(int e=first[u];e;e=nnext[e]){
			if(w[e]>0&&lev[to[e]]==-1){
				lev[to[e]]=lev[u]+1;
				que[++q]=to[e];
				if(to[e]==des){
					return 1;
				}
			}
		}
	}
	return 0;
}
int dinic(int u,int flow){
	int res=0,delta;
	if(u==des){
		return flow;
	}
	for(int &e=cur[u];e;e=nnext[e]){
		if(w[e]>0&&lev[u]<lev[to[e]]){
			delta=dinic(to[e],min(w[e],flow-res));
			if(delta){
				w[e]-=delta;
				w[e^1]+=delta;
				res+=delta;
				if(res==flow){
					break;
				}
			}
		}
	}
	if(res!=flow){
		lev[u]=-1;
	}
	return res;
}
int main(){
	int a,b,c,m;
	long long ans=0;
	scanf("%d%d%d%d",&n,&m,&src,&des);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,0);
	}
	while(bfs()){
		ans+=dinic(src,1e9);
	}
	printf("%lld",ans);
}

费用流

Dinic+SPFA

#include<bits/stdc++.h>
using namespace std;
int n,tot=1,first[500010],nnext[1000010],to[1000010],w[1000010],que[50010],src,des,cur[50010],dis[50010],vis[50010],cost[1000010];
long long sum;
void add(int x,int y,int z,int r){
	nnext[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
	cost[tot]=r;
}
int bfs(){
	int q=1,u;
	memset(que,0,sizeof(que));
	for(int i=1;i<=n;i++){
		if(i==src){
			dis[i]=0;
			vis[i]=0;
			continue;
		}
		dis[i]=1e9;
		vis[i]=0;
	}
	que[1]=src;
	for(int l=1;l<=q;l++){
		u=que[l];
		vis[u]=0;
		for(int e=first[u];e;e=nnext[e]){
			if(w[e]&&dis[u]+cost[e]<dis[to[e]]){
				dis[to[e]]=dis[u]+cost[e];
				if(vis[to[e]]==0){
					que[++q]=to[e];
					vis[to[e]]=1;
				}
			}
		}
	}
	if(dis[des]==1e9){
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(dis[i]!=1e9){
			cur[i]=first[i];
			vis[i]=0;
		}
	}
	return 1;
}
int dinic(int u,int flow){
	int res=0,delta;
	if(u==des){
		sum+=dis[des]*flow;
		return flow;
	}
	vis[u]=1;
	for(int &e=cur[u];e;e=nnext[e]){
		if(w[e]>0&&vis[to[e]]==0&&dis[u]+cost[e]==dis[to[e]]){
			delta=dinic(to[e],min(w[e],flow-res));
			if(delta){
				w[e]-=delta;
				w[e^1]+=delta;
				res+=delta;
				if(res==flow){
					break;
				}
			}
		}
	}
	if(res==flow){
		vis[u]=0;
	}
	return res;
}
int main(){
	int a,b,c,d,m;
	long long ans=0;
	scanf("%d%d%d%d",&n,&m,&src,&des);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		add(a,b,c,d);
		add(b,a,0,-d);
	}
	while(bfs()){
		ans+=dinic(src,1e9);
	}
	printf("%lld %lld",ans,sum);
}

无源汇有上下界可行流

先强制流下界,然后建超级源汇分别向流入大于流出和流出大于流入的连边。看是否满流。

#include<bits/stdc++.h>
using namespace std;
int tot=1,src,des,minu,maxu,first[210],nnext[21010],to[21010],cur[210],lev[210],d[210],w[21010],c[10210];
queue<int>q;
void add(int x,int y,int z){
	nnext[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
void build(int x,int y,int a,int b){
	add(x,y,b-a);
	add(y,x,0);
	d[x]-=a;
	d[y]+=a;
}
bool bfs(){
	int u;
	for(int i=minu;i<=maxu;i++){
		lev[i]=-1;
		cur[i]=first[i];
	}
	while(!q.empty()){
		q.pop();
	}
	q.push(src);
	lev[src]=0;
	while(!q.empty()){
		u=q.front();
		q.pop();
		for(int e=first[u];e;e=nnext[e]){
			if(w[e]>0&&lev[to[e]]==-1){
				q.push(to[e]);
				lev[to[e]]=lev[u]+1;
				if(to[e]==des){
					return 1;
				}
			}
		}
	}
	return 0;
}
int dinic(int u,int flow){
	int res=0,delta;
	if(u==des){
		return flow;
	}
	for(int &e=cur[u];e;e=nnext[e]){
		if(w[e]>0&&lev[to[e]]>lev[u]){
			delta=dinic(to[e],min(w[e],flow-res));
			if(delta){
				res+=delta;
				w[e]-=delta;
				w[e^1]+=delta;
				if(res==flow){
					break;
				}
			}
		}
	}
	if(res!=flow){
		lev[u]=-1;
	}
	return res;
}
int main(){
	int n,ss,tt,m,sum=0,a,b,dd;
	minu=1;
	scanf("%d%d",&n,&m);
	ss=n+1;
	tt=maxu=n+2;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a,&b,&c[i],&dd);
		build(a,b,c[i],dd);
	}
	for(int i=1;i<=n;i++){
		if(d[i]>0){
			add(ss,i,d[i]);
			add(i,ss,0);
			sum+=d[i];
		}
		else{
			add(i,tt,-d[i]);
			add(tt,i,0);
		}
	}
	src=ss;
	des=tt;
	while(bfs()){
		sum-=dinic(src,1e9);
	}
	if(sum){
		printf("NO");
		return 0;
	}
	printf("YES\n");
	for(int i=1;i<=m;i++){
		printf("%d\n",w[2*i+1]+c[i]);
	}
}

有源汇有上下界最大流

原汇到源连 INF 边,跑无源汇,再从原来的源到汇增广。

#include<bits/stdc++.h>
using namespace std;
int tot=1,src,des,minu,maxu,first[210],nnext[20510],to[20510],cur[210],lev[210],d[210],w[20510];
queue<int>q;
void add(int x,int y,int z){
	nnext[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
void build(int x,int y,int a,int b){
	add(x,y,b-a);
	add(y,x,0);
	d[x]-=a;
	d[y]+=a;
}
bool bfs(){
	int u;
	for(int i=minu;i<=maxu;i++){
		lev[i]=-1;
		cur[i]=first[i];
	}
	while(!q.empty()){
		q.pop();
	}
	q.push(src);
	lev[src]=0;
	while(!q.empty()){
		u=q.front();
		q.pop();
		for(int e=first[u];e;e=nnext[e]){
			if(w[e]>0&&lev[to[e]]==-1){
				q.push(to[e]);
				lev[to[e]]=lev[u]+1;
				if(to[e]==des){
					return 1;
				}
			}
		}
	}
	return 0;
}
int dinic(int u,int flow){
	int res=0,delta;
	if(u==des){
		return flow;
	}
	for(int &e=cur[u];e;e=nnext[e]){
		if(w[e]>0&&lev[to[e]]>lev[u]){
			delta=dinic(to[e],min(w[e],flow-res));
			if(delta){
				res+=delta;
				w[e]-=delta;
				w[e^1]+=delta;
				if(res==flow){
					break;
				}
			}
		}
	}
	if(res!=flow){
		lev[u]=-1;
	}
	return res;
}
int main(){
	int n,s,t,ss,tt,m,sum=0,a,b,c,dd;
	minu=1;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	ss=n+1;
	tt=maxu=n+2;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a,&b,&c,&dd);
		build(a,b,c,dd);
	}
	for(int i=1;i<=n;i++){
		if(d[i]>0){
			add(ss,i,d[i]);
			add(i,ss,0);
			sum+=d[i];
		}
		else{
			add(i,tt,-d[i]);
			add(tt,i,0);
		}
	}
	add(t,s,1e9);
	add(s,t,0);
	src=ss;
	des=tt;
	while(bfs()){
		sum-=dinic(src,1e9);
	}
	if(sum){
		printf("please go home to sleep");
		return 0;
	}
	src=s;
	des=t;
	while(bfs()){
		sum+=dinic(src,1e9);
	}
	printf("%d",sum);
}

练习:P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

有源汇有上下界最小流

同有源汇有上下界最大流,第一次满流后断掉汇到源的边从汇到源退流。

#include<bits/stdc++.h>
using namespace std;
int tot=1,src,des,minu,maxu,first[50010],nnext[500510],to[500510],cur[50010],lev[50010];
long long d[50010],w[500510];
queue<int>q;
void add(int x,int y,long long z){
	nnext[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
void build(int x,int y,long long a,long long b){
	add(x,y,b-a);
	add(y,x,0);
	d[x]-=a;
	d[y]+=a;
}
bool bfs(){
	int u;
	for(int i=minu;i<=maxu;i++){
		lev[i]=-1;
		cur[i]=first[i];
	}
	while(!q.empty()){
		q.pop();
	}
	q.push(src);
	lev[src]=0;
	while(!q.empty()){
		u=q.front();
		q.pop();
		for(int e=first[u];e;e=nnext[e]){
			if(w[e]>0&&lev[to[e]]==-1){
				q.push(to[e]);
				lev[to[e]]=lev[u]+1;
				if(to[e]==des){
					return 1;
				}
			}
		}
	}
	return 0;
}
long long dinic(int u,long long flow){
	long long res=0,delta;
	if(u==des){
		return flow;
	}
	for(int &e=cur[u];e;e=nnext[e]){
		if(w[e]>0&&lev[to[e]]>lev[u]){
			delta=dinic(to[e],min(w[e],flow-res));
			if(delta){
				res+=delta;
				w[e]-=delta;
				w[e^1]+=delta;
				if(res==flow){
					break;
				}
			}
		}
	}
	if(res!=flow){
		lev[u]=-1;
	}
	return res;
}
int main(){
	int n,s,t,ss,tt,m,a,b;
	long long c,dd,sum=0;
	minu=1;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	ss=n+1;
	tt=maxu=n+2;
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld%lld",&a,&b,&c,&dd);
		build(a,b,c,dd);
	}
	for(int i=1;i<=n;i++){
		if(d[i]>0){
			add(ss,i,d[i]);
			add(i,ss,0);
			sum+=d[i];
		}
		else{
			add(i,tt,-d[i]);
			add(tt,i,0);
		}
	}
	add(t,s,1e9);
	add(s,t,0);
	src=ss;
	des=tt;
	while(bfs()){
		sum-=dinic(src,1e9);
	}
	if(sum){
		printf("please go home to sleep");
		return 0;
	}
	src=t;
	des=s;
	sum=w[tot];
	w[tot]=w[tot^1]=0;
	while(bfs()){
		sum-=dinic(src,1e9);
	}
	printf("%lld",sum);
}

有源汇有上下界可行费用流

有源汇有上下界可行流+SPFA

#include<bits/stdc++.h>
using namespace std;
int tot=1,sum,minu,maxu,src,des,first[310],nnext[200010],to[200010],w[200010],cost[200010],cur[310],d[310],dis[310],vis[310];
queue<int>q;
void add(int x,int y,int z,int c){
	nnext[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
	cost[tot]=c;
}
void build(int x,int y,int a,int b,int c){
	add(x,y,b-a,c);
	add(y,x,0,-c);
	d[x]-=a;
	d[y]+=a;
}
bool bfs(){
	int u;
	while(!q.empty()){
		q.pop();
	}
	for(int i=minu;i<=maxu;i++){
		dis[i]=1e9;
		vis[i]=0;
	}
	dis[src]=0;
	q.push(src);
	while(!q.empty()){
		u=q.front();
		q.pop();
		vis[u]=0;
		for(int e=first[u];e;e=nnext[e]){
			if(w[e]>0&&dis[u]+cost[e]<dis[to[e]]){
				dis[to[e]]=dis[u]+cost[e];
				if(vis[to[e]]==0){
					q.push(to[e]);
					vis[to[e]]=1;
				}
			}
		}
	}
	if(dis[des]==1e9){
		return 0;
	}
	for(int i=minu;i<=maxu;i++){
		if(dis[i]!=1e9){
			vis[i]=0;
			cur[i]=first[i];
		}
	}
	return 1;
}
int dinic(int u,int flow){
	int res=0,delta;
	if(u==des){
		sum+=dis[des]*flow;
		return flow;
	}
	vis[u]=1;
	for(int &e=cur[u];e;e=nnext[e]){
		if(w[e]>0&&vis[to[e]]==0&&dis[u]+cost[e]==dis[to[e]]){
			delta=dinic(to[e],min(flow-res,w[e]));
			if(delta){
				res+=delta;
				w[e]-=delta;
				w[e^1]+=delta;
				if(res==flow){
					break;
				}
			}
		}
	}
	if(res==flow){
		vis[u]=0;
	}
	return res;
}
int main(){
	int n,m,a,b;
	scanf("%d",&n);
	des=maxu=n+2;
	for(int i=1;i<=n;i++){
		scanf("%d",&m);
		while(m--){
			scanf("%d%d",&a,&b);
			build(i,a,1,1e5,b);
			sum+=b;
		}
		if(i>=2){
			build(i,n+1,0,1e5,0);
		}
	}
	for(int i=1;i<=n;i++){
		if(d[i]>0){
			add(src,i,d[i],0);
			add(i,src,0,0);
		}
		else{
			add(i,des,-d[i],0);
			add(des,i,0,0);
		}
	}
	add(n+1,1,1e5,0);
	add(1,n+1,0,0);
	while(bfs()){
		dinic(src,1e9);
	}
	printf("%d",sum);
}

练习:P4311 士兵占领

建模

匹配问题

建出二分图跑网络流即可。

练习:

带限制匹配

拆点,出点与入点之间连流量为限制的边。

练习:

带限制覆盖

无限制的连成一条链,源流出限制这么多流量。

或者离散化后每个点向下一个点连边,区间再连一连。

练习:

分配成两个集合并产生不同贡献

先全部都选,两边建新点向贡献涉及的点建边,然后减去最小割。

练习:

棋盘上的各种问题

考虑染色,然后转化为上述几种问题。

练习:

有限制函数值分配

一般是某几个点函数值与其他某些地方的值的差大于或小于某个值。

考虑最小割。每个点拆成函数值域个,在限制涉及的两列点中间连流量为 INF 的正向或反向边。

练习:

任务利益与机器花费问题

最大权闭合子图。源向正点权的点连流量为点权的边,负点权的点向汇连流量为点权相反数的边。原图中的点权看情况。一般设为 INF。

练习:

标签:int,res,模型,网络,笔记,add,tot,lev,delta
From: https://www.cnblogs.com/zhicheng123/p/17646428.html

相关文章

  • C语言笔记 - “%”符号的用法
    1、%-运算符%表示取模运算,也就是取余数。例如6%4=22、%-引导符/占位符引导符用于控制输入输出的格式。常见于printf("%d",a);scanf("%d",&a);语句。%s - 字符串 (String)%c - 字符 (Char)%d - 十进制有符号型输出 (Decimal)①%6d整数输出,宽度是6位,不足左边补......
  • 学习网络安全好就业吗?
    学习任何技术,就业问题一直都是关注的焦点,因为不是每一门技术就业形式都很好,有时入行即失业,供大于求。目前,说到转行学技术,热度最高的莫过于网络安全行业,那么学习网络安全好就业吗?这是很多人都比较关注的问题,接下来为大家详细介绍一下。从目前市场情况来讲,网络安全岗位相对......
  • BERT模型的历史
    BERT(BidirectionalEncoderRepresentationsfromTransformers)是自然语言处理领域的一个重要里程碑。以下是BERT的发展历史概述:背景:在BERT之前,研究者们已经开始认识到预训练模型在多种任务中的潜力。例如,UlmFit、ELMo和OpenAI的GPT都是使用大型文本数据进行预训练,然后微调到......
  • 二分图笔记
    二分图定义二分图是一张无向图,可以分成\(2\)个集合\(A\)和\(B\)。在同一个集合中的点没有边相连。二分图判定当且仅当图中不存在奇数环时,该图为二分图。证明:反证法,构造一个奇数环。容易发现无论如何都不可能使相邻\(2\)点分到\(2\)个集合。那么很容易想到一个判定二......
  • 8.21 随笔记录
    高速CAN和低速CAN的区别高速CAN和低速CAN的物理层电气特性不一样,因此不能互相连接高速CAN主要应用于发动机、变速箱等实时性要求高的场合低速CAN主要应用于车身控制系统等可靠性要求高的场合CAN_H和CAN_L任意一根导线损坏,高速CAN收发失效,而低速CAN收有效,因此低速CAN的可靠性......
  • 学习笔记411—【词向量基础】:one-hot
    【词向量基础】:one-hot词向量(wordvector),也叫词嵌入(wordembedding),是一种词表征形式,将词从符号形式映射为向量形式,渐渐演变成了一种知识表示的方法。将词语从符号表示形式转换为了向量表示形式,方便了机器对自然语言的计算,因此,词向量几乎成为了所有自然语言处理和理解的下游任务的......
  • 概率与数学期望笔记
    概率论样本点:一个随机试验的某种可能的结果。样本空间\(Ω\):所有可能结果构成的集合随机事件\(A\):在一个给定的样本空间中,样本空间的子集,即由多个样本点构成的集合。随机变量\(P(A)\):把样本点映射为实数的函数,分为离散型、连续型。离散型随机变量的取值为有限或实数。我们......
  • RTSP/Onvif流媒体服务器EasyNVR安防视频平台一直提示网络请求失败的问题解决方案
    EasyNVR平台优秀的视频能力在于通过RTSP/ONVIF协议,将前端接入设备的音视频资源进行采集,并转码成适合全平台、全终端分发的视频流格式,包括RTMP、RTSP、FLV、HLS、WebRTC等格式。有用户反馈,EasyNVR使用过程中,突然提示网络请求失败,视频也无法播放,请求我们协助排查。此前我......
  • halcon 笔记 算子
    1.read_image()*读取图像11.pngread_image(Image,‘11.png’)   *计算图像的通道数count_channels(Image,Num)*循环读取每个通道的图像forindex:=1toNumby1*获取多通道图像中指定的通道图像access_channel(Image,channel,index)endfor*分解通道decompos......
  • 使用 UCS(On-Premises) 管理您的GPU资源池,释放AI大模型算力潜能
    本文分享自华为云社区《使用UCS(On-Premises)管理您的GPU资源池,释放AI大模型算力潜能》,作者:云容器大未来。AI技术现状及发展趋势过去十余年,依托全球数据、算法、算力持续突破,人工智能全面走向应用,已成为社会生产生活的支柱性技术。2020年后,当自动驾驶、人脸识别等热门应用发......