【算法笔记】上下界网络流

  • 本文为博主原创，未经许可不得转载

无源汇可行流

模型

首先建立超级源$SS$和超级汇$TT$，然后对于一条<$x,y$>容量为$[b,c]$的弧，我们对该弧进行改造

连接一条<$SS,y$>容量为$b$的弧，连接一条<$x,TT$>容量为$b$的弧，然后把<$x,y$>的容量设置为$c-b$

　　

　　

图示

　　

　　

解释

通俗来讲，就是强行给$y$结点流进$b$的流量，强行从$x$结点流出$b$的流量，使得流量下界满足要求

然后<$x,y$>的$c-b$点流量就可以不受限制地随便流了，我们称之为自由流

如果与$SS$和$TT$相连的弧全部满流，则说明有可行流

理解了这个，下面的模型就是水到渠成了

　　

　　

例题

【LYIO#156】无源汇可行流

这是真·模板题

放个代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 210
#define INF 1e9
using namespace std;
struct node{int y,next,v;}e[80010];
int n,m,S,T,flag,len(1),Link[MAXN],level[MAXN],pos[40010],ans[40010];
queue<int>q;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(int x,int y,int v){
	e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;
	e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;
}
bool bfs(){
	memset(level,-1,sizeof(level));
	q.push(S);  level[S]=0;
	while(!q.empty()){
		int x=q.front();  q.pop();
		for(int i=Link[x];i;i=e[i].next)if(level[e[i].y]==-1&&e[i].v)
			level[e[i].y]=level[x]+1,q.push(e[i].y);
	}
	return level[T]>=0;
}
int MAXFLOW(int x,int flow){
	if(x==T)  return flow;
	int d=0,maxflow=0;
	for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
		if(level[e[i].y]==level[x]+1&&e[i].v)
			if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow)))
				e[i].v-=d,e[i^1].v+=d,maxflow+=d;
	if(!maxflow)  level[x]=-1;
	return maxflow;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  S=0;  T=n+1;
	for(int i=1;i<=m;++i){
		int x=read(),y=read(),b=read(),c=read();
		insert(x,y,c-b);  pos[i]=len;  ans[i]=b;
		insert(S,y,b);  insert(x,T,b);
	}
	while(bfs()) while(MAXFLOW(S,INF));
	for(int i=Link[S];i;i=e[i].next)if(e[i].v)flag=1;
	for(int i=Link[T];i;i=e[i].next)if(e[i^1].v)flag=1;
	puts(flag?"NO":"YES");
	if(!flag)for(int i=1;i<=m;++i)printf("%d\n",e[pos[i]].v+ans[i]);
	return 0;
}

　　

　　

　　

有源汇最大流

模型

设源为$S$，汇为$T$

首先连接一条<$T,S$>的弧，流量为$+oo$，然后按照无源汇可行流的建模方法判断是否存在可行流

若存在可行流，则在残余网络上跑一遍从$S$到$T$的最大流，就是原图的最大流

　　

　　

解释

有源汇和无源汇的区别在于源点和汇点不满足流量平衡，所以我们建立弧<$T,S$>，使得源点和汇点满足流量平衡

这样就可以按照无源汇来求可行流了

跑完可行流之后，图中各条弧已经满足了流量下界的限制，所以只需要跑一边从$S$到$T$的最大流就是所求的答案

　　

　　

例题

【LYOI#157】有源汇最大流

这道也是真·模板题

贴个代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 250
#define INF 1e9
using namespace std;
struct node{int y,next,v;}e[60010];
int n,m,S,T,SS,TT,flag,len(1),Link[MAXN],level[MAXN];
queue<int>q;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(int x,int y,int v){
	e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;
	e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;
}
bool bfs(int S,int T){
	memset(level,-1,sizeof(level));
	q.push(S);  level[S]=0;
	while(!q.empty()){
		int x=q.front();  q.pop();
		for(int i=Link[x];i;i=e[i].next)if(level[e[i].y]==-1&&e[i].v)
			level[e[i].y]=level[x]+1,q.push(e[i].y);
	}
	return level[T]>=0;
}
int MAXFLOW(int x,int flow,int T){
	if(x==T)  return flow;
	int d=0,maxflow=0;
	for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
		if(level[e[i].y]==level[x]+1&&e[i].v)
			if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow),T))
				e[i].v-=d,e[i^1].v+=d,maxflow+=d;
	if(!maxflow)  level[x]=-1;
	return maxflow;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  S=read();  T=read();  SS=0;  TT=n+1;
	for(int i=1;i<=m;++i){
		int x=read(),y=read(),b=read(),c=read();
		insert(x,y,c-b);  insert(SS,y,b);  insert(x,TT,b); 
	}
	insert(T,S,INF);  int d=0,ans=0;
	while(bfs(SS,TT)) while(MAXFLOW(SS,INF,TT));
	for(int i=Link[SS];i;i=e[i].next)if(e[i].v)flag=1;
	for(int i=Link[TT];i;i=e[i].next)if(e[i^1].v)flag=1;
	if(flag) {puts("please go home to sleep");  return 0;}
	while(bfs(S,T)) while(d=MAXFLOW(S,INF,T)) ans+=d;
	printf("%d\n",ans);
	return 0;
}

　　

　　

　　

有源汇最小流

建模

首先按照无源汇可行流的方法建模，在图上跑$SS$到$TT$的最大流

然后添加弧<$T,S$>容量为$+oo$，然后再跑$SS$到$TT$的最大流就是答案

　　

　　

解释

因为这条弧对应了图中从S流向T的流量，所以我们要求原图的最小流，就要保证的流量最小

所以我们要尽量多的消耗掉不需要经过的流量

在添加弧之前跑SS到TT的最大流能做到这点

　　

　　

例题

【LYOI#158】有源汇最小流

直接上代码，但是注意，我的程序有点问题，被卡了一组超时，但大体思路无误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 50010
#define INF 1e9
using namespace std;
struct node{int y,next,v;}e[900000];
int n,m,S,T,SS,TT,flag,len(1),Link[MAXN],level[MAXN];
queue<int>q;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(int x,int y,int v){
	e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;
	e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;	
}
bool bfs(int S,int T){
	memset(level,-1,sizeof(level));
	q.push(S);  level[S]=0;
	while(!q.empty()){
		int x=q.front();  q.pop();
		for(int i=Link[x];i;i=e[i].next)if(level[e[i].y]==-1&&e[i].v)
			level[e[i].y]=level[x]+1,q.push(e[i].y);
	}
	return level[T]>=0;
}
int MAXFLOW(int x,int flow,int T){
	if(x==T)  return flow;
	int maxflow=0,d=0;
	for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
		if(level[e[i].y]==level[x]+1&&e[i].v)
			if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow),T))
				e[i].v-=d,e[i^1].v+=d,maxflow+=d;
	if(!maxflow)  level[x]=-1;
	return maxflow;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  S=read();  T=read();  SS=0;  TT=n+1;
	for(int i=1;i<=m;++i){
		int x=read(),y=read(),b=read(),c=read();
		insert(SS,y,b);  insert(x,TT,b);  insert(x,y,c-b);
	}
	while(bfs(SS,TT)) while(MAXFLOW(SS,INF,TT));
	insert(T,S,INF);  int ans=0,d=0;
	while(bfs(SS,TT)) while(d=MAXFLOW(SS,INF,TT)) ans+=d;
	for(int i=Link[SS];i;i=e[i].next)if(e[i].v)flag=1;
	for(int i=Link[TT];i;i=e[i].next)if(e[i^1].v)flag=1;
	if(flag)  puts("please go home to sleep");
	else printf("%d\n",ans);
	return 0;
}

　　

　　

　　

参考文献

  • 《算法竞赛入门经典——训练指南》——刘汝佳
  • 《上下界网络流建模方法总结》——stdcall 传送门

本文标题:【算法笔记】上下界网络流

文章作者:chty

发布时间:2017年04月24日 - 19时58分

最后更新:2018年07月09日 - 20时18分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
  1. 1. 无源汇可行流
    1. 1.1. 模型
    2. 1.2. 图示
    3. 1.3. 解释
    4. 1.4. 例题
  2. 2. 有源汇最大流
    1. 2.1. 模型
    2. 2.2. 解释
    3. 2.3. 例题
  3. 3. 有源汇最小流
    1. 3.1. 建模
    2. 3.2. 解释
    3. 3.3. 例题
  4. 4. 参考文献
,