网络流学习笔记

2023-10-12 12:08:04

什么是网络流？

网络流是一种类比水流的解决问题方法。

可以这么理解，有一个水流网络，每一条边都有一个最大承载流量。

若源点拼命放水，求最终汇点能够获得多少水。

接下来我们通过几道例题来讲解网络流算法

P3376 【模板】网络最大流

我们以题目给的这张图为例：

网络流学习笔记

我们先介绍比较简单的算法：

\(\tt{EK算法}\)​

前置芝士：

  • 流量：一条路径的流量为这条路径上边权的最小值
  • 最大流：一张图汇点可获得的最大流量
  • 增广路：指从源点到汇点的另外一条路径，且此路径所通过的流量比之前所找到的路径的流量大，则称此路径为一条增广路

由增广路和最大流的概念可知，最大流问题可以转化成不断求解增广路的问题。当一张图中找不出增广路时，就找到了此图的最大流。

对于求增广路，我们可以不断从源点开始广搜，通过权值大于 \(0\) 的边，直到搜到汇点为止

之所以是通过权值大于 \(0\) 的边呢，是因为我们在找到一条增广路之后我们将这条路上的边权都减去最小流量。容易证明，这是正确的。

寻找增广路代码：

inline bool bfs() {
	queue<int> q;
	memset(inque,false,sizeof(inque));
	memset(pre,-1,sizeof(pre));
	inque[s]=true;
	q.push(s);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=head[u],v;i;i=edge[i].nxt) {
			v=edge[i].to;
			ll w=edge[i].w;
			if(!inque[v] && w) {
				pre[v].lst=u;
				pre[v].pos=i;
				if(v==t)
					return true;
				inque[v]=true;
				q.push(v);
			}
		}
	}
	return false;
}

那个 \(pre\) 数组是用来记录前驱的，\(lst\) 代表前驱点，\(pos\) 代表前驱边

然后我们不断寻找最大流，累加流量

代码（错误的）：

inline void EK() {
	while(bfs()) { // 一直找增广路
		ll flow=inf;
		for(int i=t;i!=s;i=pre[i].lst)
			flow=min(flow,edge[pre[i].pos].w); // 计算流量
		for(int i=t;i!=s;i=pre[i].lst)
			edge[pre[i].pos].w-=flow; // 减去流量，便于计算增广路
		ans+=flow; // 累计流量
	}
}

为什么这是错误的

我们来看这张图

网络流学习笔记

如果第一次找到的增广路是 \(1 \to 2 \to 3 \to 4\)​​​​​ ,那之后就找不到增广路了，求出的最大流是 \(1\)。显然此图的最大流是 \(2\)，这个答案是错误的。

我们引入一个反向边的概念，即在建每一条边时再建一条边权为 \(0\) 的反向边。

现在建完边的图是这样的：

网络流学习笔记

在找到一条增广路之后，我们将这条边上的边权都减去最小流量，同时我们将这条边的反向边上的边权都加上最小流量

有什么意义呢？

这相当于我们多了一个反悔操作。

例如，我们先找到一条增广路（非样例）为 \(1 \to 2 \to 4 \to 6\)​ ，利用反向边我们发现 \(4\) 这个点可以直接到达 \(3\)​​ ，那我们就可以利用反向边改变这条路径。

所以说，反向边就是做一个标记，让后面的增广路有机会让前面的增广路改变，从而保证答案的正确性。

本题完整代码：

#include <queue>
#include <cstdio>
#include <cstring>
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
using namespace std;
const ll inf=1e18;
const int N=2e2+7,M=5e3+7;

struct Edge {
	int nxt,to;
	ll w;
}edge[M<<1];

struct Pre {
	int lst,pos;
}pre[N];

int head[M<<1],tot=1;
bool inque[N];

ll ans;
int n,m,s,t;

inline void AddEdge(int u,int v,ll w) {
	edge[++tot].nxt=head[u];
	edge[tot].to=v;
	edge[tot].w=w;
	head[u]=tot;
}

inline bool bfs() {
	queue<int> q;
	memset(inque,false,sizeof(inque));
	memset(pre,-1,sizeof(pre));
	inque[s]=true;
	q.push(s);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=head[u],v;i;i=edge[i].nxt) {
			v=edge[i].to;
			ll w=edge[i].w;
			if(!inque[v] && w) { // !inque[v]是用来判断边权和为0的环的
				pre[v].lst=u;
				pre[v].pos=i; // 记录增广路
				if(v==t) // 找到增广路,返回
					return true; 
				inque[v]=true;
				q.push(v);
			}
		}
	}
	return false;
}

inline void EK() {
	while(bfs()) { // 一直找增广路
		ll flow=inf;
		for(int i=t;i!=s;i=pre[i].lst)
			flow=min(flow,edge[pre[i].pos].w); // 计算流量
		for(int i=t;i!=s;i=pre[i].lst) {
			edge[pre[i].pos].w-=flow; // 减去流量，便于计算增广路
			edge[pre[i].pos^1].w+=flow;
		}
		ans+=flow; // 累计流量
	}
}

signed main() {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1,u,v;i<=m;++i) {
		ll w;
		scanf("%d%d%lld",&u,&v,&w);
		AddEdge(u,v,w);
		AddEdge(v,u,0);
	}
	EK();
	printf("%lld",ans);
    return 0;
}

P3381 【模板】最小费用最大流

网络流学习笔记

（其实就是最大流+最短路

如何实现？

很简单，将 BFS 改成 SPFA 就行了

注意一下，建边时反向边的花费为正向边的相反数，因为返回时你要退钱！！！

所以就有了负边权，用 SPFA 方便一点

完整代码：

#include <queue>
#include <cstdio>
#include <cstring>
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e3+7,M=5e4+7;

struct Edge {
	int nxt,to;
	int w,price;
}edge[M<<1];

struct Pre {
	int lst;
	int pos;
}pre[N];

int head[N];
int dis[N];
bool inque[N];

int n,m,s,t;
int tot=1,ans,cost;

inline void AddEdge(int u,int v,int w,int p) {
	edge[++tot].nxt=head[u];
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].price=p;
	head[u]=tot;
}

inline bool SPFA() { // 用 SPFA 寻找费用最小的增广路
	memset(pre,0,sizeof(pre));
	memset(dis,inf,sizeof(dis));
	memset(inque,false,sizeof(inque));
	queue<int> q;
	q.push(s);
	inque[s]=true;
	dis[s]=0;
	while(!q.empty()) {
		int u=q.front();
		q.pop(),inque[u]=false;
		for(int i=head[u],v,p;i;i=edge[i].nxt) {
			v=edge[i].to,p=edge[i].price;
			if(edge[i].w>0 && dis[v]>dis[u]+p) {
				dis[v]=dis[u]+p;
				pre[v].lst=u;
				pre[v].pos=i;
				if(!inque[v]) {
					q.push(v);
					inque[v]=true;
				}
			}
		}
	}
	return dis[t]!=inf;
}

inline void EK() {
	while(SPFA()) {
		int minn=inf;
		for(int i=t;i!=s;i=pre[i].lst)
			minn=min(minn,edge[pre[i].pos].w);
		for(int i=t;i!=s;i=pre[i].lst) {
			edge[pre[i].pos].w-=minn;
			edge[pre[i].pos^1].w+=minn;
		}
		ans+=minn;
		cost+=minn*dis[t];
	}
}

signed main() {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1,u,v,w,p;i<=m;++i) {
		scanf("%d%d%d%d",&u,&v,&w,&p);
		AddEdge(u,v,w,p);
		AddEdge(v,u,0,-p); // 注意建边
	}
	EK();
	printf("%d %d",ans,cost);
    return 0;
}

其实用 Dijkstra 也可以，建边的时候改一下就行了，建议学一下 Johnson

接下来我们介绍一个新的算法：

\(\tt{Dinic算法}\)

我们先来看一下 EK 算法有什么缺点？

很显然，EK 算法在寻找增广路是只能一条一条地找，那我们有没有算法可以一次找很多条呢？

Dinic 算法就可以实现多路增广，它分为两个步骤：bfs 分层 + dfs 增广

在 Dinic 算法中，我们的 bfs给每一个点分层，即标记处源点到每个点的最少经过点数。

代码：

inline bool bfs() {
	queue<int> q;
	memset(deep,0,sizeof(deep));
	q.push(s);
	deep[s]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=head[u],v;i;i=edge[i].nxt) {
			v=edge[i].to;
			if(!deep[v] && edge[i].w) {
				deep[v]=deep[u]+1;
				q.push(v);
			}
		}
	}
	return deep[t];
}

接下来我们用 dfs 增广

代码：

inline ll dfs(int u,ll flow) {
	if(u==t)
		return flow;
	ll outflow=0;
	for(int i=head[u],v;i && flow;i=edge[i].nxt) {
		v=edge[i].to;
		ll w=edge[i].w;
		if(w && deep[v]==deep[u]+1) {
			ll res=dfs(v,min(flow,w));
			edge[i].w-=res;
			edge[i^1].w+=res;
			flow-=res;
			outflow+=res;
		}
	}
	if(!outflow) // 如果这个点无法向汇点继续传输，那么就不必经过这个点，为这个点打上一个标记
		deep[u]=0;
	return outflow;
}

为什么代码中会有一行 deep[v]==deep[u]+1呢？

这时候分层的作用就体现出来了，有了这一行，我们就可以保证我们找的是最短增广路，大大缩短了我们返回重新找的次数

当前弧优化

我们加入一个 \(cur\) 数组，功能有点类比邻接表的 \(head\)​ 数组，它会随着 dfs 而修改

每次我们找过某条边时，修改 \(cur\)​ 数组，改成该边的编号,换句话说就是走过的边不走了

原理：我们在 dfs 时，先遍历的边肯定已经被增广过了（或无法继续增广），这条边就没有用了，我们利用 \(cur\)​ 数组，抛弃这些没有用的边，效率就会大大提升。

当然，我们在用 EK 算法求费用流时也是可以用上弧优化的。

完整代码：

#include <queue>
#include <cstdio>
#include <cstring>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
using namespace std;
const ll inf=1e18;
const int N=2e2+7,M=5e3+7;

struct Edge {
	int nxt,to;
	ll w;
}edge[M<<1];

int head[M],cur[N],tot=1;
int deep[N];
bool inque[N];

ll ans;
int n,m,s,t;

inline void AddEdge(int u,int v,ll w) {
	edge[++tot].nxt=head[u];
	edge[tot].to=v;
	edge[tot].w=w;
	head[u]=tot;
}

inline bool bfs() {
	queue<int> q;
	memset(deep,0,sizeof(deep));
	q.push(s);
	deep[s]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=head[u],v;i;i=edge[i].nxt) {
			cur[u]=head[u];
			v=edge[i].to;
			if(!deep[v] && edge[i].w) {
				deep[v]=deep[u]+1;
				q.push(v);
			}
		}
	}
	return deep[t];
}

inline ll dfs(int u,ll flow) {
	if(u==t)
		return flow;
	ll outflow=0;
	for(int i=cur[u],v;i && flow;i=edge[i].nxt) {
		cur[u]=i;
		v=edge[i].to;
		ll w=edge[i].w;
		if(w && deep[v]==deep[u]+1) {
			ll res=dfs(v,min(flow,w));
			edge[i].w-=res;
			edge[i^1].w+=res;
			flow-=res;
			outflow+=res;
		}
	}
	if(!outflow) // 如果这个点无法向汇点继续传输，那么就不必经过这个点，为这个点打上一个标记
		deep[u]=0;
	return outflow;
}

inline void Dinic() {
	while(bfs())
		ans+=dfs(s,inf);
}

signed main() {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1,u,v;i<=m;++i) {
		ll w;
		scanf("%d%d%lld",&u,&v,&w);
		AddEdge(u,v,w);
		AddEdge(v,u,0);
	}
	Dinic();
	printf("%lld",ans);
    return 0;
}
上一篇：tomcat是什么？Tomcat 下载、安装、配置图文教程


下一篇：Linux本地yum源配置以及使用yum源安装gcc编译环境