juju527's blog

因为失去，所以明白

网络流

发布于 2020-04-21 | 分类于 网络流 、 学习笔记 | 36分钟 | 7154字数 | 浏览量：

网络流

一个网络是一张有向图，
图中每条边(x,y)都有一个给定的权值c(x,y)，称为边的容量
还有两个特别的点S,T分别称为源点和汇点

f(x,y)是定义在节点二元组(x,y)上的实数函数称为流函数
流函数有以下性质

1.f(x,y)<=c(x,y)2.f(x,y)=−f(y,x)3.∀x≠S,x≠T,Σ(u,x)∈Ef(u,x)=Σ(x,v)∈Ef(x,v)1.f(x,y)<=c(x,y)\\ 2.f(x,y)=-f(y,x)\\ 3.\forall x \neq S,x\neq T,\Sigma_{(u,x)\in E}f(u,x)=\Sigma_{(x,v)\in E}f(x,v)

三条性质分别称为容量限制，斜对称和流量守恒

而流量守恒告诉我们网络中除了源点和汇点外，任何节点不存储流
其流入总量等于流出总量

而网络流模型可以形象的描述为：
在不超过容量限制的前提下，“流”从源点源源不断的产生，流经整个网络，最终全部归于汇点

对于一条E中的(x,y)，f(x,y)称为边的流量，c(x,y)-f(x,y)称为边的剩余容量

Σ(S,v)∈Ef(s,v)称为整个网络的流量\Sigma_{(S,v)\in E}f(s,v)称为整个网络的流量

注意
每条边的反向边都有一个负的流量

最大流

对于给定的一个网络，合法的流函数很多
使得整个网络的流量最大的流函数被称为网络的最大流

Edmond-Karp增广路算法

若一条从源点到汇点的路径各边上剩余容量均大于0
则称这条路径为一条增广路
EK算法的思想就是通过不断bfs找增广路知道图中不存在增广路
至于反向边的作用
考虑"可撤销贪心", 建立一条反向边来反悔.
因为反向边相当于把正向边的流又推了回去
关于EK
最坏情况下时间复杂度为O(n*m^2)
一般能处理n=1000至10000的数据规模
但有可能被卡

【模板】网络最大流

板子

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005,maxm=100005;
const int inf=0x3f3f3f3f;
struct Edge{
	int to,w;
	int nxt;
}e[2*maxm];
int cnt;
int head[maxn];
int n,m,s,t;
int ans=0;
int vis[maxn];
int incf[maxn];
int pre[maxn];
queue<int>q;
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void add(int u,int v,int w){
	e[cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt++;
	e[cnt].to=u;e[cnt].w=0;e[cnt].nxt=head[v];head[v]=cnt++;
}
bool bfs(){
	memset(vis,0,sizeof(vis));
	while(!q.empty())q.pop();
	q.push(s);vis[s]=1;
	incf[s]=inf;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i=head[k];i!=-1;i=e[i].nxt){
			int tmp=e[i].to;
			if(e[i].w<=0)continue;
			if(vis[tmp])continue;
			incf[tmp]=min(incf[k],e[i].w);
			pre[tmp]=i;
			q.push(tmp);
			vis[tmp]=1;
			if(tmp==t)return 1;
		}
	}
	return 0;
}
void update(){
	int x=t;
	while(x!=s){
		int i=pre[x];
		e[i].w-=incf[t];
		e[i^1].w+=incf[t];
		x=e[i^1].to;
	}
	ans+=incf[t];
	return ;
}
int main()
{
	n=read();
	m=read();
	s=read();
	t=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int u,v,w;
		u=read();
		v=read();
		w=read();
		add(u,v,w);
	}
	while(bfs())update();
	printf("%d",ans);
	return 0;
}

Dinic算法

在任意时刻
网络中所有节点以及剩余容量大于0的边构成的子图被称为残量网络
前文提及的EK算法每轮可能遍历整个残量网络，但只找出一条增广路
时间复杂度不够优
那么我们就想要每次bfs或者dfs时找出多条增广路
我们通过建立分层图来增加效率
每次只走向下一层
这样我们走的一定是最短路
时间复杂度经过大佬们的证明，不超过O(n^2 *m)

bool bfs(){
	memset(lev,0,sizeof(lev));
	while(!q.empty())q.pop();
	q.push(s);
	lev[s]=1;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i=head[k];i!=-1;i=e[i].nxt){
			int tmp=e[i].to;
			if(e[i].w==0||lev[tmp])continue;
			lev[tmp]=lev[k]+1;//分层
			q.push(tmp);
			if(tmp==t)return 1;//还能到达，且其他还没有分层的点目前没有意义了，return即可
		}
	}
	return 0;//无法到达
}
int dinic(int x,int flow){//我们遍历到了x节点，从s到x的路径的最大流量为flow
	if(x==t)return flow;//找到了一条增广路
	int rest=flow;//剩余最多可以分配到接下来的点的流量
	for(int i=head[x];i!=-1;i=e[i].nxt){
		if(!rest)break;//没有可以分配的流量了，走人
		int tmp=e[i].to;
		if(e[i].w==0||lev[tmp]!=lev[x]+1)continue;//走最短路，且走0边权没有意义
		int inc=dinic(tmp,min(rest,e[i].w));//算出从s到x，x到t的最大流量，增广路已找到
		if(!inc)lev[tmp]=0;//如果走tmp得不到流量可以证明走tmp不会再对答案有贡献，层次设为0
		e[i].w-=inc;
		e[i^1].w+=inc;
		rest-=inc;//给这条路径分配了inc的流量
	}
	return flow-rest;//分配下去的流量
}
	while(bfs()){
		int flow=dinic(s,inf);
		while(flow){
			maxflow+=flow;
			flow=dinic(s,inf);
		}
	}

最小费用最大流

【模板】最小费用最大流

与最大流相比，费用流每条边多了一个“费用”的权值
我们需要在分配流量的方案为最大流的前提下求最小总费用

注意这里的费用指单位流量的费用，每条边的此值可能不一样

这里和最大流想法差不多，多了一个费用的处理
想要费用最小，跑出一条s到t的最短路
记下最短路的路径
更新流量边权
建边时注意(u,v)的反边的费用应是-c，c为费用
这同样是为了保证反悔机制

最短路用什么算法呢
spfa
因为图中有负权值
并且就算spfa死了
达到n^2的复杂度
我们也无所为，毕竟网络流复杂度太高了
综上我们可以认为spfa在费用流里活过来了

我们对于费用流跑dinic还是EK呢
答案是后者
因为我们找路经是通过一个spfa来实现的
这时将图分层毫无意义，达不到优化的用途
而且EK还更好写，更好理解

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=50005,maxm=500005,inf=0x3f3f3f3f3f3f3f3f;
struct Edge{
	int to,w,co;
	int nxt;
}e[2*maxm];
int cnt;
int head[maxn];
int n,m,s,t;
int maxflow,mincost;
int inc[maxn],cot[maxn];
int pre[maxn];
bool vis[maxn];
queue<int>q;
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void add(int u,int v,int w,int f){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].co=f;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
bool spfa(){
	memset(vis,0,sizeof(vis));
	memset(inc,0,sizeof(inc));
	memset(cot,0x3f,sizeof(cot));
	while(!q.empty())q.pop();
	q.push(s);
	vis[s]=1;inc[s]=inf;cot[s]=0;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		vis[k]=0;
		for(int i=head[k];i!=-1;i=e[i].nxt){
			int tmp=e[i].to;
			if(e[i].w==0||cot[tmp]<=cot[k]+e[i].co)continue;
			inc[tmp]=min(inc[k],e[i].w);
			cot[tmp]=cot[k]+e[i].co;
			pre[tmp]=i;
			if(!vis[tmp]){q.push(tmp);vis[tmp]=1;}
		}
	}
	return cot[t]<inf;
}
void update(){
	int p=t;
	while(p!=s){
		int edge=pre[p];
		e[edge].w-=inc[t];
		e[edge^1].w+=inc[t];
		p=e[edge^1].to;
	}
	maxflow+=inc[t];
	mincost+=inc[t]*cot[t];
	return ;
}
signed main(){
	n=read();m=read();s=read();t=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read(),f=read();
		add(u,v,w,f);
		add(v,u,0,-f);
	}
	while(spfa())update();
	printf("%lld %lld",maxflow,mincost);
	return 0;
}

网络流进阶

最小割等于最大流
并不严谨的证明这一点
最小割：割去最小的边集使得S到T不连通
考虑我们找增广路求最大流的过程
只要我们还存在一条增广路
即还存在一条从S到T的路径
那么我们会把这条增广路径流满
可以理解为我们在这条路径上割去了那条限制路径流量的边
即这条路径上的最小边
最小割是想要割去某些边使得S到T不连通且割去的边权总和最小
那么我们还存在一条路径，就一定不行，需要砍掉某条边

由于网络流也经常用来跑一个二分图
我们这里引入一些二分图的定义和定理

二分图最大匹配数：对于一个二分图选取最多的边使得没有边有重复的节点

最小点覆盖数：选择最少的节点，使每一条边都至少有一个点被选中

最大点独立集数：选择最多的节点，使每一条边都至多有一个点被选中

最大匹配数等于最大流
考虑多添一个源点和汇点
二分图一边连源点一边连汇点
所有边流量都为1
这样保证一条边最多过一次
显而易见，此时该图最大流等于原二分图最大匹配数

最小点覆盖数等于最大匹配数

最小点覆盖数+最大点独立集数等于总点数

最大权闭合子图
我们有一个有向图
若存在一个点集使得点集内任意x所能到达的节点都在该点集里
我们称这样的点集为闭合子图
最大权闭合子图即所有闭合子图中权值和最大的那个
权值显然有正有负
我们考虑建图
S连向所有正点权的点，容量为点权
所有负点权的点连向T，容量为点权的相反数
原图中的边容量为inf
然后求最小割
最大权闭合子图的权值即为所有正点权的和减去最小割
正确性就是说
我们求最小割
那么就是割掉某些边使图S到T不连通
由于原图的边都是inf
我们肯定割不掉
那割的边一定是连源点或汇点的边
我们割连汇点的边代表我们支付这个负的权值，即选了某一个闭合子图包含整个负权节点
我们割连源点的边代表我们不得到这个正的权值，即我们没有选任何一个包含该正权节点的闭合子图
是否会存在我们选了某个闭合子图而没割掉左边的负权边呢？
这是不存在的
若我们选了所有这个闭合子图的正权节点，那么一定能流到每一个这个闭合子图的负权节点
若某一个负权节点未割去，那么图一定还联通
由于我们求的是最小割
所以得到的也是最大权闭合子图

[NOI2009]植物大战僵尸
考虑我们想吃掉(x,y)
那么我们一定要先吃掉所有保护(x,y)的点和(x,y+1)
当然当y=m-1使后面的条件就不需要了
每一个点向所有它的先决点连边
我们考虑这样建出一个有向图来
我们求最大权闭合子图就是答案了
但是这样的图可能有环
这样的话我们跑最大权闭合子图就可能不对
因为只要在环里的点我们是无论如何也吃不掉的
同时，所有被环内点保护的点我们也吃不掉
由于这个被环内点保护的点我们不好找到
考虑建一个反图，再跑一边topo
这样做完所有没被topo到的点就是环内点或被环保护的点了
然后所有跟这些点有关的点我们都不建到网络流的图中
再对网络流图跑最大权闭合子图就可以了

#include<bits/stdc++.h>
using namespace std;
const int maxn=25,maxm=35,inf=0x3f3f3f3f;
struct Edge{
	int to,w;
	int nxt;
}e[maxn*maxm*maxn*maxm];
int cnt;
int head[maxn*maxm];
int n,m;
int ans=0;
int s,t;
int lev[maxn*maxm];
int a[maxn*maxm];
int rd[maxn*maxm];
bool vis[maxn*maxm];
vector<int>g[maxn*maxm];
queue<int>q;
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void topo(){
	for(int i=1;i<=n*m;i++)
		if(!rd[i])
			q.push(i);
	while(!q.empty()){
		int k=q.front();
		q.pop();
		vis[k]=1;
		for(int i=0;i<g[k].size();i++){
			int tmp=g[k][i];
			rd[tmp]--;
			if(!rd[tmp])q.push(tmp);
		}
	}
}
void add(int u,int v,int w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
void addedge(){
	s=1;t=n*m+2;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n*m;i++){
		if(!vis[i])continue;
		if(a[i]>0){
			ans+=a[i];
			add(s,i+1,a[i]);
			add(i+1,s,0);
		}
		else{
			add(i+1,t,-a[i]);
			add(t,i+1,0);
		}
		for(int j=0;j<g[i].size();j++){
			int tmp=g[i][j];
			if(!vis[tmp])continue;
			add(tmp+1,i+1,inf);
			add(i+1,tmp+1,0);
		}
	}
	return ;
}
bool bfs(){
	memset(lev,0,sizeof(lev));
	while(!q.empty())q.pop();
	q.push(s);
	lev[s]=1;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i=head[k];i!=-1;i=e[i].nxt){
			int tmp=e[i].to;
			if(e[i].w==0||lev[tmp])continue;
			lev[tmp]=lev[k]+1;
			q.push(tmp);
			if(tmp==t)return 1;
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t)return flow;
	int rest=flow;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		if(!rest)break;
		int tmp=e[i].to;
		if(e[i].w==0||lev[tmp]!=lev[x]+1)continue;
		int inc=dinic(tmp,min(rest,e[i].w));
		if(!inc)lev[tmp]=0;
		e[i].w-=inc;
		e[i^1].w+=inc;
		rest-=inc;
	}
	return flow-rest;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n*m;i++){
		int w;
		a[i]=read();
		w=read();
		for(int j=1;j<=w;j++){
			int pos=read()*m+read()+1;
			rd[pos]++;
			g[i].push_back(pos);
		}
		if((i%m)!=1){
			rd[i-1]++;
			g[i].push_back(i-1);
		}
	}
	topo();
	addedge();
	int maxflow=0;
	while(bfs()){
		int flow=dinic(s,inf);
		while(flow){
			maxflow+=flow;
			flow=dinic(s,inf);
		}
	}
	printf("%d\n",ans-maxflow);
	return 0;
}

[六省联考2017]寿司餐厅
这个题比较恶心
我们发现你想拿到di,jd_{i,j}
就必须拿到di−1,jd_{i-1,j}和di,j−1d_{i,j-1}
那么这样的先决条件让我们想到最大权闭合子图
而我们又思考题中的“记忆性”
即不重复计算dd值
这也很符合最大权闭合子图的做法
我们先建好上面的图
考虑计算费用
我们只需在每个di,id_{i,i}的节点后面建一个aia_i的点
这个aia_i的点连向TT一条aia_i的边
我们就可以搞定cxcx的问题
然后对于每一个不同的aia_i值，都建一个节点用来计算m∗x2m*x^2
就是每一个刚才的aia_i节点都连向这个aia_i对应计算m∗x2m*x^2的节点一条infinf的边
然后这个点连TT一条m∗x2m*x^2的边即可
其他建图就参照最大权闭合子图的套路建法即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=105,maxa=1005,inf=0x3f3f3f3f;
struct Edge{
	int to,w;
	int nxt;
}e[2*maxn*maxn+2*maxa*maxn];
int cnt;
int head[maxn*maxn];
int num=0;
int s,t,ans=0;
int lev[maxn*maxn];
int p[maxa];
int id[maxn][maxn];
queue<int>q;
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void add(int u,int v,int w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
bool bfs(){
	memset(lev,0,sizeof(lev));
	while(!q.empty())q.pop();
	q.push(s);
	lev[s]=1;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i=head[k];i!=-1;i=e[i].nxt){
			int tmp=e[i].to;
			if(e[i].w==0||lev[tmp])continue;
			lev[tmp]=lev[k]+1;
			q.push(tmp);
			if(tmp==t)return 1;
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t)return flow;
	int rest=flow;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		if(!rest)break;
		int tmp=e[i].to;
		if(e[i].w==0||lev[tmp]!=lev[x]+1)continue;
		int inc=dinic(tmp,min(rest,e[i].w));
		if(!inc)lev[tmp]=0;
		e[i].w-=inc;
		e[i^1].w+=inc;
		rest-=inc;
	}
	return flow-rest;
}
int main(){
	int n,m;
	n=read();m=read();
	memset(head,-1,sizeof(head));
	s=++num;t=++num;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			id[i][j]=++num;
	for(int i=1;i<=n;i++){
		int val;
		val=read();
		int k=++num;
		add(id[i][i],k,inf);
		add(k,id[i][i],0);
		if(!p[val]){
			p[val]=++num;
			add(p[val],t,m*val*val);
			add(t,p[val],0);
		}
		add(k,p[val],inf);
		add(p[val],k,0);
		add(k,t,val);
		add(t,k,0);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<n-i+1;j++){
			int val=read();
			if(val>0){
				ans+=val;
				add(s,id[i][i+j],val);
				add(id[i][i+j],s,0);
			}
			else{
				add(id[i][i+j],t,-val);
				add(t,id[i][i+j],0);
			}
			if(!j)continue;
			add(id[i][i+j],id[i][i+j-1],inf);
			add(id[i][i+j-1],id[i][i+j],0);
			add(id[i][i+j],id[i+1][i+j],inf);
			add(id[i+1][i+j],id[i][i+j],0);
		}
	}
	int maxflow=0;
	while(bfs()){
		int flow=dinic(s,inf);
		while(flow){
			maxflow+=flow;
			flow=dinic(s,inf);
		}
	}
	printf("%d",ans-maxflow);
	return 0;
}

无源汇上下界可行流

模板
没有源点和汇点，每条边有流量上界和下界，问是否可行
即能否在满足限制的情况下流量守恒
考虑到麻烦的东西在于下界
因为我们之前做的网络流都是只带容量(上界)的
那么我们能把下界的限制去除掉吗？
我们把原图的每条边的上下界限制改成我们熟悉的单个上界限制
(u,v,up,down)变为(u,v,up-down)
那么即我们默认这条边流了down这么多的流量
这条边再流流量的话就代表在下界的基础上多一些流量，同时多的流量不超过up-down
我们定义in[i],out[i]两个数组
表示直接与i相连的边中指向i的边的下界流量之和，与指出i的边的下界流量之和
那么in[i]和out[i]会有一个大小关系
对于一个点i
in[i]>out[i]那么代表i流入的最少流量比i流出的最小流量大
即我们要将out这一边的某些边的流量变大以使得流量守恒
而out这边需要变大的应该是in[i]-out[i]
那么这in[i]-out[i]的流量那里来呢，我们考虑将超级源点连向i，容量为in[i]-out[i]
这些流量流过去就会让从i出去的边流量增大
那么in[i]<out[i]呢
我们考虑将i连向超级汇点容量为out[i]-in[i]
那么照最大流的原则
我们会尽可能流满直接到达t的边/从s出去的边
也就是in这边的边的流量想要多out[i]-in[i]
可行的条件即为新图最大流跑满了所有从s出去的边
这里简单证明一下从s出去的边的总容量等于到达t的边的总容量

∑ini=∑outi∑i∈ini−outi>0(ini−outi)=∑i∈outi−ini>0(outi−ini)\sum in_i=\sum out_i\\ \sum_{i\in in_i-out_i>0} (in_i-out_i)=\sum_{i\in out_i-in_i>0}(out_i-in_i)

如果跑不满那流量就无法守恒，即不可行
附板子

#include<bits/stdc++.h>
using namespace std;
const int maxn=205,maxm=10205;
const int inf=0x3f3f3f3f;
struct Edge{
	int to,w;
	int nxt;
}e[2*maxm+2*maxn];
int cnt;
int head[maxn];
int n,m,s,t,ans=0;
int in[maxn],out[maxn];
int maxflow;
int lev[maxn];
int low[2*maxm];
queue<int>q;
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void add(int u,int v,int w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
bool bfs(){
	memset(lev,0,sizeof(lev));
	while(!q.empty())q.pop();
	q.push(s);
	lev[s]=1;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i=head[k];i!=-1;i=e[i].nxt){
			int tmp=e[i].to;
			if(e[i].w==0||lev[tmp])continue;
			lev[tmp]=lev[k]+1;
			q.push(tmp);
			if(tmp==t)return 1;
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t)return flow;
	int rest=flow;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		if(!rest)break;
		int tmp=e[i].to;
		if(e[i].w==0||lev[tmp]!=lev[x]+1)continue;
		int inc=dinic(tmp,min(rest,e[i].w));
		if(!inc)lev[tmp]=0;
		e[i].w-=inc;
		e[i^1].w+=inc;
		rest-=inc;
	}
	return flow-rest;
}
int main(){
	n=read();m=read();
	s=n+1,t=n+2;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int u,v,lower,upper;
		u=read();v=read();lower=read();upper=read();
		in[v]+=lower;
		out[u]+=lower;
		low[cnt]=lower;
		add(u,v,upper-lower);
		add(v,u,0);
	}
	for(int i=1;i<=n;i++){
		if(in[i]==out[i])continue;
		if(in[i]>out[i]){
			add(s,i,in[i]-out[i]);
			add(i,s,0);
		}
		else{
			add(i,t,out[i]-in[i]);
			add(t,i,0);
		}
		ans+=in[i]>out[i]?in[i]-out[i]:0;
	}
	while(bfs()){
		int flow=dinic(s,inf);
		while(flow){
			maxflow+=flow;
			flow=dinic(s,inf);
		}
	}
	if(maxflow<ans){printf("NO");return 0;}
	printf("YES\n");
	for(int i=0;i<=2*m-2;i+=2)
		printf("%d\n",e[i^1].w+low[i]);
	return 0;
}

有源汇有上下界最大流

考虑先变成无源汇的可行流判断是否可行
由于原图中的源汇点不需遵守流量守恒
我们连一条(t,s)的边使t出去的和t进来的相等，s进来的和s出去的相等
跑完之后这条新边经过的流量即为原图的一个可行的流量(不是可行流)
我们想跑出最大流
只要在这个基础上在把源点定为原源点s，汇点定为源汇点t，跑最大流
得到的即原图的可行的最大流
模板

#include<bits/stdc++.h>
using namespace std;
const int maxn=205,maxm=10000,inf=0x3f3f3f3f;
struct Edge{
	int to,w;
	int nxt;
}e[2*maxm+2*maxn];
int cnt;
int head[maxn];
int n,m,s,t,S,T;
int in[maxn],out[maxn];
int lev[maxn];
queue<int>q;
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void add(int u,int v,int w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
bool bfs(int start,int end){
	memset(lev,0,sizeof(lev));
	while(!q.empty())q.pop();
	q.push(start);
	lev[start]=1;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		for(int i=head[k];i!=-1;i=e[i].nxt){
			int tmp=e[i].to;
			if(e[i].w==0||lev[tmp])continue;
			lev[tmp]=lev[k]+1;
			q.push(tmp);
			if(tmp==end)return 1;
		}
	}
	return 0;
}
int dinic(int x,int end,int flow){
	if(x==end)return flow;
	int rest=flow;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		if(!rest)break;
		int tmp=e[i].to;
		if(e[i].w==0||lev[tmp]!=lev[x]+1)continue;
		int inc=dinic(tmp,end,min(rest,e[i].w));
		if(!inc)lev[tmp]=0;
		e[i].w-=inc;
		e[i^1].w+=inc;
		rest-=inc;
	}
	return flow-rest;
}
int main(){
	int sum=0;
	n=read();m=read();s=read();t=read();
	S=n+1;T=n+2;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int u,v,lower,upper;
		u=read();v=read();lower=read();upper=read();
		in[v]+=lower;
		out[u]+=lower;
		add(u,v,upper-lower);
		add(v,u,0);
	}
	for(int i=1;i<=n;i++){
		if(in[i]==out[i])continue;
		if(in[i]>out[i]){
			add(S,i,in[i]-out[i]);
			add(i,S,0);
		}
		else{
			add(i,T,out[i]-in[i]);
			add(T,i,0);
		}
		sum+=(in[i]-out[i]>0?in[i]-out[i]:0);
	}
	add(t,s,inf);
	add(s,t,0);
	int maxflow=0;
	while(bfs(S,T)){
		int flow=dinic(S,T,inf);
		while(flow){
			maxflow+=flow;
			flow=dinic(S,T,inf);
		}
	}
	if(maxflow<sum){printf("please go home to sleep");return 0;}
	maxflow=e[cnt].w;
	while(bfs(s,t)){
		int flow=dinic(s,t,inf);
		while(flow){
			maxflow+=flow;
			flow=dinic(s,t,inf);
		}
	}
	printf("%d",maxflow);
	return 0;
}

有源汇有上下界最小流

跑一边可行流
添(t,s,inf)边
再跑一边可行流
添边中的流量即为答案

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int maxn=50100,maxm=125100;
const long long inf=0x3f3f3f3f3f3f3f3f;
struct Edge{
	int to;
	long long w;
	int nxt;
}e[2*maxm+2*maxn];
int cnt;
int head[maxn];
int n,m,s,t,S,T;
long long in[maxn],out[maxn];
int lev[maxn];
queue<int>q;
inline long long read(){
	register long long x=0,y=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
inline void add(register int u,register int v,register long long w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
inline bool bfs(register int start,register int end){
	memset(lev,0,sizeof(lev));
	while(!q.empty())q.pop();
	q.push(start);
	lev[start]=1;
	while(!q.empty()){
		register int k=q.front();
		q.pop();
		for(register int i=head[k];i!=-1;i=e[i].nxt){
			register int tmp=e[i].to;
			if(e[i].w==0||lev[tmp])continue;
			lev[tmp]=lev[k]+1;
			q.push(tmp);
			if(tmp==end)return 1;
		}
	}
	return 0;
}
inline long long dinic(register int x,register int end,register long long flow){
	if(x==end)return flow;
	register long long rest=flow;
	for(register int i=head[x];i!=-1;i=e[i].nxt){
		if(!rest)break;
		register int tmp=e[i].to;
		if(e[i].w==0||lev[tmp]!=lev[x]+1)continue;
		register long long inc=dinic(tmp,end,min(rest,e[i].w));
		if(!inc)lev[tmp]=0;
		e[i].w-=inc;
		e[i^1].w+=inc;
		rest-=inc;
	}
	return flow-rest;
}
int main(){
	register long long sum=0;
	n=read();m=read();s=read();t=read();
	S=n+1;T=n+2;
	memset(head,-1,sizeof(head));
	for(register int i=1;i<=m;i++){
		register int u,v,lower,upper;
		u=read();v=read();lower=read();upper=read();
		in[v]+=lower;
		out[u]+=lower;
		add(u,v,upper-lower);
		add(v,u,0);
	}
	for(register int i=1;i<=n;i++){
		if(in[i]==out[i])continue;
		if(in[i]>out[i]){
			add(S,i,in[i]-out[i]);
			add(i,S,0);
		}
		else{
			add(i,T,out[i]-in[i]);
			add(T,i,0);
		}
		sum+=in[i]-out[i]>0?in[i]-out[i]:0;
	}
	register long long maxflow=0;
	while(bfs(S,T)){
		register int flow=dinic(S,T,inf);
		while(flow){
			maxflow+=flow;
			flow=dinic(S,T,inf);
		}
	}
	add(t,s,inf);
	add(s,t,0);
	while(bfs(S,T)){
		register int flow=dinic(S,T,inf);
		while(flow){
			maxflow+=flow;
			flow=dinic(S,T,inf);
		}
	}
	if(maxflow<sum){printf("please go home to sleep");return 0;}
	printf("%lld",e[cnt-1].w);
	return 0;
}

有源汇有上下界费用流

这里的费用流不要求是最大/小流，只需费用最大/小
[AHOI2014/JSOI2014]支线剧情
因为此题是一个树
故每个点都走到，就是每条边都走到
即该边下界为1上界为inf，费用为过该条边所需的时间
然后源点向1连(0,inf,0)边，每一个点向汇点连(0,inf,0)边
我们想求此图的有源汇有上下界最小费用流
对该图跑可行流(最小费用最大流)
然后答案即为跑出来的费用加上每条边下界流量乘费用

#include<bits/stdc++.h>
using namespace std;
const int maxn=305,inf=0x3f3f3f3f;
struct Edge{
	int to,w,f;
	int nxt;
}e[2*55*maxn];
int cnt;
int head[maxn];
int s,t,S,T;
int mincost;
int in[maxn],out[maxn];
int inc[maxn],dis[maxn],pre[maxn];
bool vis[maxn];
queue<int>q;
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
void add(int u,int v,int w,int f){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].f=f;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
	return ;
}
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	q.push(S);
	inc[S]=inf;dis[S]=0;vis[S]=1;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		vis[k]=0;
		for(int i=head[k];i!=-1;i=e[i].nxt){
			int tmp=e[i].to;
			if(e[i].w==0||dis[tmp]<=dis[k]+e[i].f)continue;
			inc[tmp]=min(inc[k],e[i].w);
			dis[tmp]=dis[k]+e[i].f;
			pre[tmp]=i;
			if(!vis[tmp])q.push(tmp);vis[tmp]=1;
		}
	}
	return dis[T]<inf;
}
void update(){
	int p=T;
	while(p!=S){
		int edge=pre[p];
		e[edge].w-=inc[T];
		e[edge^1].w+=inc[T];
		p=e[edge^1].to;
	}
	mincost+=inc[T]*dis[T];
	return ;
}
int main(){
	int n;
	n=read();
	s=n+1;t=n+2;S=n+3;T=n+4;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++){
		int k;
		k=read();
		for(int j=1;j<=k;j++){
			int v,tim;
			v=read();tim=read();
			mincost+=tim;
			in[v]++;
			out[i]++;
			add(i,v,inf-1,tim);
			add(v,i,0,-tim);
		}
	}
	add(s,1,inf,0);
	add(1,s,0,0);
	for(int i=1;i<=n;i++){
		add(i,t,inf,0);
		add(t,i,0,0);
	}
	for(int i=1;i<=n;i++){
		if(in[i]==out[i])continue;
		if(in[i]>out[i]){
			add(S,i,in[i]-out[i],0);
			add(i,S,0,0);
		}
		else{
			add(i,T,out[i]-in[i],0);
			add(T,i,0,0);
		}
	}
	add(t,s,inf,0);
	add(s,t,0,0);
	while(spfa())update();
	printf("%d",mincost);
	return 0;
}
# 网络流 # 学习笔记
线段树合并 上一篇
概率与期望 下一篇
0%