专栏文章

举若学习网络流的note

AAC_notonlyAC
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minvavl5
此快照首次捕获于
2025/12/02 08:56
3 个月前
此快照最后确认于
2025/12/02 08:56
3 个月前
查看原文

网络流

定义

什么是网络流？OI wiki 上的定义长这样：
实际意思就是：一张有向图，有一个 源点 SS 和 汇点 TT ，每两条边之间都有一个容量，流经这条边的流量不能超过该边的容量（可以将容量看作水管的容积）。要求从源点流出去多少就要在汇点流回来多少（因此不能存在50的流量从50容量的边流到30容量的边被卡了20，只能有30的流量从50容量的边流到30容量的边）。流到一个点若有分叉可以对流量进行分配，分配不同的流量至不同的路径上。
可以类比着城市的水网图来理解。

最大流

最大流就是在这张网络上源点可以流出的最大流量。
偷一张模板的图：
本图中源点为 4，汇点为 3。
一种最大流的分配方式为：
  • 4→2→34 \to 2 \to 3 通过 20 的流量
  • 4→34 \to 3 通过 20 的流量
  • 4→2→1→34 \to 2 \to 1 \to 3 通过 10 的流量，不能直接通过 30 的流量是因为第一次操作中已经将 4→24 \to 2 这条边的容量消耗了 20 了，仅剩 10 的容量
因此最大流为 20 + 20 + 10 = 50 。这是一种方式。
有哪些算法可以实现呢？
先引入几个概念：
残量网络：指所有节点和当前状态下所有还有容量残余的边组成的子网络（子图）。
增广路：一条在残量网络上从起点到汇点的路径，即这条路径上的每条边都还有剩余容量（容量均不为 0）。
那么我们肯定要给所有仍然是增广路的路流流量，也就是给所有仍然是增广路的路增广。但很明显，有时这样的贪心是错的，比如：
我们可能会先选择 1→2→3→41 \to 2 \to 3 \to 4 这条路，但很明显，这样的流量只有 3，而选择 1→3→41 \to 3 \to 4 和 1→2→41 \to 2 \to 4 的流量为 6。这时我们可以在 2 和 3 之间建立一条反边，初始容量为 0，当一条边的容量减少时，让这条边的反向边增加对应的容量。因此，一次增广路经过了某条反向边，就相当于给原边退流了。
在这张图中，原先选择 1→2→3→41 \to 2 \to 3 \to 4 这条路流了 3 的流量，此时正向边 2→32 \to 3 的容量降至 2，反向边 3→23 \to 2 的容量就变成 3 了。此时再走一条 1→3→2→41 \to 3 \to 2 \to 4 的路，流过 3 的流量（相当于原来 2→32 \to 3 退流了），正好最大流就是 3 + 3 = 6。是不是很神奇呢！
在这样的图上，能增广就增广看起来就很对了。

Edmonds−Karp 算法

由此便诞生了一种较为暴力的算法：只要还有增广边就 bfs，不停止。时间复杂度是 O(nm2)O(nm^2) 的，具体操作见模版题P3376 的代码：
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,s,t,flag[2005][2005],tot=1;
ll head[10005],tail[10005],nxt[10005],vl[10005],dis[10005],pre[10005],ans;
void add(ll u,ll v,ll w)
{
	tail[++tot]=v;
	vl[tot]=w;
	nxt[tot]=head[u];
	head[u]=tot;
  //建反边
	tail[++tot]=u;
	vl[tot]=0;
	nxt[tot]=head[v];
	head[v]=tot;
//上面tot=1就是为了凑{2,3}这样一对异或1为其反向边的一组边
}
bool vis[10005];
bool bfs()
{
	for(ll i=1;i<=n;i++) vis[i]=0;//每次操作都清空，只找一条路
	vis[s]=1;
	dis[s]=1e18;
	queue<ll> q;
	q.push(s);
	while(q.size())
	{
		ll u=q.front();
		q.pop();
		for(ll i=head[u];i;i=nxt[i])
		{
			if(vl[i]==0) continue;
			ll v=tail[i];
			if(vis[v]==1) continue;
			dis[v]=min(dis[u],vl[i]);
			pre[v]=i;
			q.push(v);
			vis[v]=1;
			if(v==t) return 1;
		}
	}
	return 0;
}
void update()
{
	ll x=t;
	while(x!=s)
	{
		ll v=pre[x];
		vl[v]-=dis[t];//让其始终减去整条路流量最小的容量
		vl[v^1]+=dis[t];
		x=tail[v^1];
	}
	ans+=dis[t];
}
int main()
{
	cin>>n>>m>>s>>t; 
	for(ll i=1;i<=m;i++)
	{
		ll u,v,w;
		cin>>u>>v>>w;
		if(flag[u][v]==0)//判重边
		{
			add(u,v,w);
			flag[u][v]=tot-1;
		}
		else vl[flag[u][v]]+=w;
	}
	while(bfs()) update();//有就一直跑
	cout<<ans;
}
很明显，这样的时间复杂度不是很优，找一条增广路就要跑一遍图。

Dinic 算法

我们可以每次 bfs 给整个图分层，随后再利用 dfs 进行一次跑多条增广路进行增广。这样的时间复杂度为 O(n2m)O(n^2m)，稠密图比EK算法优很多，因此此算法更常用。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,s,t,tot=1,ans;
ll head[10005],tail[10005],nxt[10005],vl[10005],dis[10005];
void add(ll u,ll v,ll w)
{
	tail[++tot]=v;
	vl[tot]=w;
	nxt[tot]=head[u];
	head[u]=tot;
	tail[++tot]=u;
	vl[tot]=0;
	nxt[tot]=head[v];
	head[v]=tot;
}
ll now[10005];
bool bfs()
{
	for(ll i=1;i<=n;i++) dis[i]=1e18;//dis指的就是每个点在哪一层
	dis[s]=0;
	now[s]=head[s];//这里采用当前弧优化
	queue<ll> q;
	q.push(s);
	while(!q.empty())
	{
		ll u=q.front();
		q.pop();
		for(ll i=head[u];i;i=nxt[i])
		{
			ll v=tail[i];
			if(vl[i]==0) continue;
			if(dis[v]!=1e18) continue;
			q.push(v);
			now[v]=head[v];//这里采用当前弧优化
			dis[v]=dis[u]+1;
			if(v==t) return 1; 
		}
	}
	return 0;
}
ll dfs(ll x,ll sum)
{
	if(x==t) return sum;
	ll res=0;
	for(ll i=now[x];i&&sum;i=nxt[i])
	{
		now[x]=i;//当前弧优化
		ll v=tail[i];
		if(vl[i]>0&&(dis[v]==dis[x]+1))//有流量且是在x的下一层
		{
			ll k=dfs(v,min(sum,vl[i]));//k是当前最小的剩余容量 
			if(k==0) dis[v]=1e18;//剪枝，如果此路不通就没必要继续走下去了，不如直接删了
			vl[i]-=k;
			vl[i^1]+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}
int main()
{
	cin>>n>>m>>s>>t;
	for(ll i=1;i<=m;i++)
	{
		ll u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	while(bfs())
	{
		ans+=dfs(s,1e18);//流量可以设成无穷大，后续也会被挤掉
	}
	cout<<ans;
}
注：当前弧优化指本次 bfs 时当遍历到 xx 的第 ii 条弧时前 i−1i-1 条弧没有被遍历的需要了（该流的都留了），因此下一次直接从 xx 的第 ii 条弧开始遍历，可以省点时间。

最小费用最大流

顾名思义，就是在最大流的基础上加上最小费用，即每条边有容量和代价（流过这条边的流量与代价成正比），在满足求最大流的情况下还要满足费用最小。
很明显，最小费用实质上就是最短路，所以我们可以考虑把最短路和最大流结合起来。SPFA 和最大流都是利用 bfs 维护的，而且由于有反边，我们要将反边的费用设为负值，需要让 SPFA 来解决负环的问题，因此可以考虑与 SPFA 相结合（虽然 SPFA 很容易被卡）。
详情见代码：
CPP
#include<bits/stdc++.h>
#define ll int
using namespace std;
ll n,m,s,t,tot=1,ans,minc;
ll head[500005],tail[500005],nxt[500005],vl[500005],val[500005],dis[500005],vis[500005];
void add(ll u,ll v,ll w,ll c)
{
	tail[++tot]=v;
	vl[tot]=w;
	val[tot]=c;
	nxt[tot]=head[u];
	head[u]=tot;
	tail[++tot]=u;
	vl[tot]=0;
	val[tot]=-c;//反向边边权设为负数
	nxt[tot]=head[v];
	head[v]=tot;
}
ll now[500005];
bool spfa()
{
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=n;i++) dis[i]=1e9;
	for(ll i=1;i<=n;i++) now[i]=head[i];//这样初始化似乎更直观
	dis[s]=0;
	queue<ll> q;
	q.push(s);
	vis[s]=1;
	//cout<<s<<" ";
	while(!q.empty())
	{
		ll u=q.front();
		q.pop();
		vis[u]=0;
		for(ll i=head[u];i;i=nxt[i])
		{
			ll v=tail[i];
			if(vl[i]==0) continue;
			if(dis[v]>dis[u]+val[i])
			{
				dis[v]=dis[u]+val[i];
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
					//cout<<v<<" ";
				}
			}
		}
	}
	if(dis[t]!=1e9) return 1;
	return 0;
}
ll dfs(ll x,ll sum)
{
	if(x==t) return sum;
	ll res=0;
	vis[x]=1;
	for(ll i=now[x];i&&sum;i=nxt[i])
	{
		now[x]=i;
		ll v=tail[i];
		if(vl[i]>0&&(dis[v]==dis[x]+val[i])&&!vis[v])//同dinic，将其进行分层，vis[v]或许是为了判负环防止死循环的
		{
			ll k=dfs(v,min(sum,vl[i]));
			if(k==0) dis[v]=1e9;
			vl[i]-=k;
			vl[i^1]+=k;
			res+=k;
			sum-=k;
			minc+=k*val[i];//最小费用在这里就可以算了
		}
	}
	vis[x]=0;
	return res;
}
int main()
{
	cin>>n>>m>>s>>t;
	for(ll i=1;i<=m;i++)
	{
		ll u,v,w,c;
		cin>>u>>v>>w>>c;
		add(u,v,w,c);
	}
	while(spfa())
	{
		ans+=dfs(s,1e9);
	}
	cout<<ans<<" "<<minc;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...