首页 > 其他分享 >有上下界的网络流

有上下界的网络流

时间：2024-05-31 20:21:32浏览次数：24  
标签：int sum 网络 下界 ss addedge 汇有

顾名思义，有上下界的网络流与一般网络流相比多一个下界的限制，就是一条边的流量要满足在\([l,r]\)这个区间内。
这里一共有三个问题：
1.无源汇有上下界可行流
2.有源汇有上下界可行流
3.有源汇有上下界最大/小流
三个问题是前后关联的。
无源汇有上下界可行流
对于一条边\(u\to v\)，定义：
\(l(u,v)\)是边\(u\to v\)的下界。
\(r(u,v)\)是边\(u\to v\)的上界。
\(f(u,v)\)是边\(u\to v\)的流量。
需要满足两个条件：
1.\(\forall (u\to v)\in E,l(u,v)\le f(u,v)\le r(u,v)\)
2.\(\forall 1\le i\le n,\sum_{(u\to i)\in E} f(u,i)=\sum_{(i\to v)\in E} f(i,v)\)
设\(g(u,v)=f(u,v)-l(u,v)\)，\(a_i=\sum_{(i\to v)\in E} l(i,v)-\sum_{(u\to i)\in E} l(u,i)\)。
所以\(a_i=\sum_{(u\to i)\in E} g(u,i)-\sum_{(i\to v)\in E} g(i,v)\)。
建一个超级源点\(S\)和一个超级汇点\(T\)，如果\(a_i>0\)，则连一条\(i\to T\)的上界为\(a_i\)的边，如果\(a_i<0\)，则连一条\(S\to i\)的上界为\(-a_i\)的边。
从\(S\)到\(T\)跑一个最大流，如果\(S\)的出边和\(T\)的入边都流满，则可行。
有源汇有上下界可行流
在这张图上除了\(s\)和\(t\)，都是满足\(\sum_{(u\to i)\in E} f(u,i)=\sum_{(i\to v)\in E} f(i,v)\)。为了让\(s\)和\(t\)也满足，我们可以连一条\(t\to s\)的上界为$+\infty \(的边。这样就变成了无源汇有上下界可行流问题。 **有源汇有上下界最大/小流** 先是最大流，这里先跑一个有源汇有上下界可行流问题。将残量网络拿出来取出后加入的边\)t\to s\(，令\)A=f(t,s)\(，去掉后加入的边，再跑从\)s\(到\)t\(的最大流为\)B\(，答案为\)A+B\(。 最小流与最大流有两处不同： 1.\)B\(为从\)t\(到\)s\(的最大流。 2.答案为\)A-B$。
例题
#115. 无源汇有上下界可行流

#include<iostream>
#define INF 1000000000
using namespace std;
int kd(){
	int x=0,f=1;
	char a=getchar();
	while(a<'0'||a>'9'){
		if(a=='-'){
			f=-1;
		}
		a=getchar();
	}
	while(a>='0'&&a<='9'){
		x=x*10+a-'0';
		a=getchar();
	}
	return x*f;
}
int n,m;
struct node{
	int to;
	int nxt;
	int val;
}edge[20810];
int head[210],tot;
void addedge(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].nxt=head[u];
	edge[tot].val=w;
	head[u]=tot;
}
int a[210];
int ans[10210];
int s,t;
int dep[210];
int shu[210];
int dui[210],he,ta;
int vis[210];
void bfs(){
	he=ta=1;
	dui[1]=t;
	vis[t]=1;
	dep[t]=0;
	shu[0]++;
	while(he<=ta){
		int u=dui[he];
		he++;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(vis[v]==1){
				continue;
			}
			dui[++ta]=v;
			vis[v]=1;
			dep[v]=dep[u]+1;
			shu[dep[v]]++;
		} 
	}
}
int maxflow;
int dfs(int u,int flow){
	if(u==t){
		maxflow+=flow;
		return flow;
	}
	int used=0;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(dep[v]+1==dep[u]&&edge[i].val!=0){
			int zhi=dfs(v,min(edge[i].val,flow-used));
			if(zhi!=0){
				used+=zhi;
				edge[i].val-=zhi;
				edge[i%2==1?i+1:i-1].val+=zhi;
				if(used==flow){
					return used;
				}
			}
		}
	}
	shu[dep[u]]--;
	if(shu[dep[u]]==0){
		dep[s]=n+2;
	}
	dep[u]++;
	shu[dep[u]]++;
	return used;
}
int main(){
	cin>>n>>m;
	s=0,t=n+1; 
	for(int i=1;i<=m;i++){
		int u,v,l,r;
		u=kd();v=kd();l=kd();r=kd();
		ans[i]=l;
		a[u]+=l;
		a[v]-=l;
		addedge(u,v,r-l);
		addedge(v,u,0);
	}
	for(int i=1;i<=n;i++){
		if(a[i]==0){
			continue;
		}
		if(a[i]>0){
			addedge(i,t,a[i]);
			addedge(t,i,0);
		}
		else{
			addedge(s,i,-a[i]);
			addedge(i,s,0);
		}
	}
	bfs();
	while(dep[s]<n+2){
		dfs(s,INF);
	}
	int p=0;
	for(int i=2*m+1;i<=tot;i+=2){
		if(edge[i].val!=0){
			p=1;
			break;
		}
	}
	if(p==1){
		cout<<"NO"<<endl;
	}
	else{
		cout<<"YES"<<endl;
		for(int i=1;i<=m;i++){
			ans[i]+=edge[i*2].val;
			cout<<ans[i]<<endl;
		}
	}
	return 0;
}

#116. 有源汇有上下界最大流

#include<iostream>
#define int long long
#define INF 1000000000000000000
using namespace std;
int kd(){
	int x=0,f=1;
	char a=getchar();
	while(a<'0'||a>'9'){
		if(a=='-'){
			f=-1;
		}
		a=getchar();
	}
	while(a>='0'&&a<='9'){
		x=x*10+a-'0';
		a=getchar();
	}
	return x*f;
}
int n,m,s,t;
struct node{
	int to;
	int nxt;
	int val;
}edge[20410];
int head[210],tot;
void addedge(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].nxt=head[u];
	edge[tot].val=w;
	head[u]=tot;
}
int a[210];
int ss,tt,lin;
int dep[210];
int shu[210];
int vis[210];
int dui[210],he,ta;
void bfs(){
	he=ta=1;
	dui[1]=tt;
	vis[tt]=1;
	dep[tt]=0;
	shu[0]++;
	while(he<=ta){
		int u=dui[he];
		he++;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(vis[v]==1){
				continue;
			}
			dui[++ta]=v;
			vis[v]=1;
			dep[v]=dep[u]+1;
			shu[dep[v]]++;
		}
	}
}
int maxflow;
int dfs(int u,int flow){
	if(u==tt){
		maxflow+=flow;
		return flow;
	}
	int used=0;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(dep[v]+1==dep[u]&&edge[i].val!=0){
			int zhi=dfs(v,min(edge[i].val,flow-used));
			if(zhi!=0){
				used+=zhi;
				edge[i].val-=zhi;
				edge[i%2==1?i+1:i-1].val+=zhi;
				if(used==flow){
					return used;
				}
			}
		}
	}
	shu[dep[u]]--;
	if(shu[dep[u]]==0){
		dep[ss]=lin;
	}
	dep[u]++;
	shu[dep[u]]++;
	return used;
}
void ISAP(){
	bfs();
	while(dep[ss]<lin){
		dfs(ss,INF);
	}
}
signed main(){
	cin>>n>>m>>s>>t;
	ss=0,tt=n+1,lin=n+2;
	for(int i=1;i<=m;i++){
		int u,v,l,r;
		u=kd();v=kd();l=kd();r=kd();
		addedge(u,v,r-l);
		addedge(v,u,0);
		a[u]+=l;
		a[v]-=l;
	}
	addedge(t,s,INF);
	addedge(s,t,0);
	for(int i=1;i<=n;i++){
		if(a[i]==0){
			continue;
		}
		if(a[i]>0){
			maxflow-=a[i];
			addedge(i,tt,a[i]);
			addedge(tt,i,0);
		}
		else{
			addedge(ss,i,-a[i]);
			addedge(i,ss,0);
		}
	}
	ISAP();
	if(maxflow!=0){
		cout<<"please go home to sleep";
		return 0;
	}
	maxflow=edge[m*2+2].val;
	for(int u=ss;u<=tt;u++){
		while(head[u]>m*2){
			head[u]=edge[head[u]].nxt;
		}
	}
	for(int i=ss;i<=tt;i++){
		vis[i]=0;
		dep[i]=0;
	}
	for(int i=0;i<=lin+2;i++){
		shu[i]=0;
	}
	tot=m*2;
	ss=s,tt=t,lin=n;
	ISAP();
	cout<<maxflow;
	return 0;
}

#117. 有源汇有上下界最小流

#include<iostream>
#define int long long
#define INF 1000000000000000000
using namespace std;
int kd(){
	int x=0,f=1;
	char a=getchar();
	while(a<'0'||a>'9'){
		if(a=='-'){
			f=-1;
		}
		a=getchar();
	}
	while(a>='0'&&a<='9'){
		x=x*10+a-'0';
		a=getchar();
	}
	return x*f;
}
int n,m,s,t;
struct node{
	int to;
	int nxt;
	int val;
}edge[2600020];
int head[500010],tot;
void addedge(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].nxt=head[u];
	edge[tot].val=w;
	head[u]=tot;
}
int a[500010];
int ss,tt,lin;
int vis[500010];
int dep[500010];
int shu[500010];
int dui[500010],he,ta;
void bfs(){
	he=ta=1;
	dui[1]=tt;
	vis[tt]=1;
	dep[tt]=0;
	shu[0]++;
	while(he<=ta){
		int u=dui[he];
		he++;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(vis[v]==1){
				continue;
			}
			dui[++ta]=v;
			vis[v]=1;
			dep[v]=dep[u]+1;
			shu[dep[v]]++;
		}
	}
}
int maxflow;
int cur[50010];
int dfs(int u,int flow){
	if(u==tt){
		maxflow+=flow;
		return flow;
	}
	int used=0;
	for(int i=cur[u];i;cur[u]=i,i=edge[i].nxt){
		int v=edge[i].to;
		if(dep[v]+1==dep[u]&&edge[i].val!=0){
			int zhi=dfs(v,min(flow-used,edge[i].val));
			if(zhi!=0){
				used+=zhi;
				edge[i].val-=zhi;
				edge[i%2==1?i+1:i-1].val+=zhi;
				if(used==flow){
					return used;
				}
			}
		}
	}
	shu[dep[u]]--;
	if(shu[dep[u]]==0){
		dep[ss]=lin;
	}
	dep[u]++;
	shu[dep[u]]++;
	return used;
}
void ISAP(){
	bfs();
	while(dep[ss]<lin){
		if(ss==0){
			for(int i=0;i<=n+1;i++){
				cur[i]=head[i];
			}
		}
		else{
			for(int i=1;i<=n;i++){
				cur[i]=head[i];
			}
		}
		dfs(ss,INF);
	}
}
signed main(){
	cin>>n>>m>>s>>t;
	ss=0,tt=n+1,lin=n+2;
	for(int i=1;i<=m;i++){
		int u,v,l,r;
		u=kd();v=kd();l=kd();r=kd();
		addedge(u,v,r-l);
		addedge(v,u,0);
		a[u]+=l;
		a[v]-=l;
	} 
	addedge(t,s,INF);
	addedge(s,t,0);
	for(int i=1;i<=n;i++){
		if(a[i]==0){
			continue;
		}
		if(a[i]>0){
			maxflow-=a[i];
			addedge(i,tt,a[i]);
			addedge(tt,i,0);
		}
		else{
			addedge(ss,i,-a[i]);
			addedge(i,ss,0);
		}
	}
	ISAP();
	if(maxflow!=0){
		cout<<"please go home to sleep";
		return 0;
	}
	maxflow=-edge[m*2+2].val;
	for(int u=ss;u<=tt;u++){
		if(head[u]>2*m){
			head[u]=edge[head[u]].nxt;
		}
	}
	tot=2*m;
	for(int i=ss;i<=tt;i++){
		dep[i]=0;
		vis[i]=0;
	}
	for(int i=0;i<=lin+2;i++){
		shu[i]=0;
	}
	ss=t,tt=s,lin=n;
	ISAP();
	cout<<(-1)*maxflow;
	return 0;
}

标签：int,sum,网络,下界,ss,addedge,汇有
From： https://www.cnblogs.com/z-2-we/p/18225229

相关文章

  • 计算机网络基础知识（持续更新中）
    目录前言第一章：概述一、因特网概述二、三种交换方式三、计算机网络定义及分类前言为夯实计算机网络基础知识，本篇跟随b站的胡科大教书匠走进计算机网络的世界，仅记录计算机网络中的重点知识。第一章：概述一、因特网概述1.网络、互联网（互连网）和因特网的概念：网络：由结......
  • SNCScan：针对SAP安全网络通信（SNC）的安全分析与评估工具
    关于SNCScanSNCScan是一款针对SAP安全网络通信（SNC）的安全分析与评估工具，该工具旨在帮助广大研究人员分析SAP安全网络通信（SNC），并分析和检测SNC配置与SAP组件中的潜在问题。SNC系统参数SNC基础SAP协议，例如DIAG或RFC，本身并没有提供较高的安全保护。为了提高安全性并确保身份验......
  • 网络信息安全专业毕业找工作岗位有哪些？快来看
    前言渗透测试工程师：主要负责通过模拟黑客来对网站进行一个由头至尾的检测，在系统中发现和挖掘存在的漏洞，可以通过社工、网络扫描和密码破解、手工测试等手段进行测试，并最终出具一份渗透测试报告交予甲方网络运维者进行修补发现的漏洞。安全服务工程师：相对于其他安全工作......
  • SQLRecon：一款针对MSSQL的网络侦查与后渗透测试工具
    关于SQLReconSQLRecon是一款针对MicrosoftSQLServer的安全研究工具，该工具专为红队研究人员设计，可以帮助广大研究人员针对MSSQL执行网络侦查和后渗透利用测试。工具安装广大研究人员可以直接访问该项目的【Releases页面】下载预编译的最新版本SQLRecon。除此之外，我们还......
  • Uscrapper：一款功能强大的网络资源爬取工具
    关于UscrapperUscrapper是一款功能强大的网络资源爬取工具，该工具可以帮助广大研究人员从各种网络资源中轻松高效地提取出有价值的数据，并且提供了稳定、友好且易于使用的UI界面，是安全研究人员和网络分析人员的强有力工具。Uscrapper最大程度地释放了开源情报资源的力量，该工具......
  • 网络编程
    网络编程--客户端和服务器端客户端和服务器端实现连接和通信服务器端：通过sock套接字进行连接通信#include<WinSock2.h>#include<Windows.h>#include<iostream>#include<WS2tcpip.h>#pragmacomment(lib,"ws2_32.lib")intmain(){ //初始化网络环境 WSADATAdate{0......
  • 网络安全在2024好入行吗？
    前言023年的今天，慎重进入网安行业吧，目前来说信息安全方向的就业对于学历的容忍度比软件开发要大得多，还有很多高中被挖过来的大佬。理由很简单，目前来说，信息安全的圈子人少，985、211院校很多都才建立这个专业，加上信息安全法的存在，形成了小圈子的排他效应，大佬们的技术交流都是......
  • 目前我国网络安全人才市场状况
    网络安全人才市场状况本章以智联招聘多年来形成的丰富的招聘、求职信息大数据为基础，结合了奇安信集团在网络安全领域多年来的专业研究经验，相关研究成果具有很强的代表性。对涉及安全人才的全平台招聘需求与求职简历进行分析（注：本章中的需求指数采用的是全量数据统计，其他......
  • 【故障识别】基于CNN-SVM卷积神经网络结合支持向量机的数据分类预测研究（Matlab代码实
    ......
  • 2024年网络安全学习指南！详尽路线图，从零基础到黑客高手的进阶之路！
    零基础小白，到就业！入门到入土的网安/黑客学习路线！建议的学习顺序：一、网络安全学习普法（心里有个数，要进去坐几年！）1、了解并介绍《网络安全法》2、《全国人大常委会关于维护互联网安全的决定》3、《中华人民共和国计算机信息系统安全保护条例（2011年修正）》4、《中华人民共......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99