从零单练网络流 第三章 有上下界的可行流

2023-10-17 18:32

本文主要是介绍从零单练网络流 第三章 有上下界的可行流,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

可行流无非就是把给定的一些条件转化为最大流可以完成的任务,著名的题目有SGU上的两道题P194 Reactor Cooling和P176 Flow Construction。第一题我本想依靠自己想出最大流的模型,不过最后还是看了题解。


这里简要讲一下P194 Reactor Cooling这道题的解法,这题在ACdream上也有,P1211。题意大概为给你n个点,m条边,每条边有上下界流,然后要保证每个点出流和入流一样。

建立超级源st和超级汇tr,对于每条边的容量为自己上下界流之差,记录每个点入出流情况。假如入流多,那st到该点加一条边即多出来的入流,反之,就该点引边向tr,值是这个绝对值。至于为什么这样,只有自己模拟一遍,自己说服自己了,说实在是说不清楚。不过有一点可以帮助你理解,这道题判断是否可行,是要st每条边都满流,之前因为st的边是由入流情况决定的,而其他边是上下界之差,即其他边是忽略了下界的判断的,那所有关于下界的判断全部集中于st引出的边,st引出的边正是保证他们下界之上的关键,而上下界之差的边则控制了上界。那为什么st引出的边保证了他们下界之上呢?因为假如每条边都是下界,那有些点必溢出,这些溢出的流则由超级源提供了。上下界之差控制上界应该好理解。

你理解了吗?


Reactor Cooling的代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<queue>
#include<stack> 
#include<vector>
#include<cmath>
#include<iomanip>
#define rep(i,n) for(i=1;i<=n;i++)
#define MM(a,t) memset(a,t,sizeof(a))
#define INF 1e9
typedef long long ll;
#define mod 1000000007
using namespace std; 
int n,m,np,nc,st,tr; 
int res;
struct edge{int s,e,lest;
}eg[40020];
int w[220][220],inout[220];
int gap[220],dis[220],pre[220];
queue<int> Q;
void BFS(){int i,j;MM(gap,0); MM(dis,0);dis[tr]=0; gap[0]=1;while(!Q.empty()) Q.pop(); Q.push(tr);while(!Q.empty()){int s,e=Q.front(); Q.pop();for(s=0;s<=n;s++)if(!dis[s] && w[s][e]){dis[s]=dis[e]+1;gap[dis[s]]++; Q.push(s);}} //for(i=0;i<=n;i++) cout<<dis[i]<<' '; cout<<'\n';
}
int ISAP(){BFS();	int i,u=st,j,ans=0,md;pre[st]=-1;while(dis[u]<=n){if(u==tr){int minflow=INF;for(i=pre[u];i!=-1;u=i,i=pre[i])  minflow=min(minflow,w[i][u]);for(i=pre[u=tr];i!=-1;u=i,i=pre[i]){w[i][u]-=minflow;w[u][i]+=minflow;}	ans+=minflow;}for(i=0;i<=n;i++)if(w[u][i]>0 && dis[i]+1==dis[u]) break;if(i<=n){pre[i]=u;u=i;}else{if(--gap[dis[u]]==0) break;for(md=n,i=0;i<=n;i++)if(w[u][i]>0) md=min(md,dis[i]);dis[u]=md+1;gap[dis[u]]++;if(u!=st) u=pre[u];}}return ans;
}
int main()
{int i,j,i1,i2,i3;string si;while(scanf("%d%d",&n,&m)!=EOF){MM(w,0); MM(inout,0);rep(i,m){int s,e,v1,v2;scanf("%d%d%d%d",&s,&e,&v1,&v2);eg[i].s=s; eg[i].e=e; eg[i].lest=v1;inout[s]-=v1; inout[e]+=v1;w[s][e]=v2-v1;} st=0; tr=n+1; n++;rep(i,n-1)if(inout[i]<0) w[i][tr]=-inout[i];else           w[st][i]=inout[i];ISAP();bool ff=true;rep(i,n-1)if(w[st][i]!=0){ff=false;break;	} if(!ff) printf("NO\n");else{printf("YES\n");rep(i,m) printf("%d\n",eg[i].lest+w[eg[i].e][eg[i].s]);	}}return 0;
}


这篇关于从零单练网络流 第三章 有上下界的可行流的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/227199

相关文章

Linux中压缩、网络传输与系统监控工具的使用完整指南

《Linux中压缩、网络传输与系统监控工具的使用完整指南》在Linux系统管理中,压缩与传输工具是数据备份和远程协作的桥梁,而系统监控工具则是保障服务器稳定运行的眼睛,下面小编就来和大家详细介绍一下它... 目录引言一、压缩与解压:数据存储与传输的优化核心1. zip/unzip:通用压缩格式的便捷操作2.

Linux网络配置之网桥和虚拟网络的配置指南

《Linux网络配置之网桥和虚拟网络的配置指南》这篇文章主要为大家详细介绍了Linux中配置网桥和虚拟网络的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、网桥的配置在linux系统中配置一个新的网桥主要涉及以下几个步骤:1.为yum仓库做准备,安装组件epel-re

python如何下载网络文件到本地指定文件夹

《python如何下载网络文件到本地指定文件夹》这篇文章主要为大家详细介绍了python如何实现下载网络文件到本地指定文件夹,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下...  在python中下载文件到本地指定文件夹可以通过以下步骤实现,使用requests库处理HTTP请求,并结合o

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解