专栏文章

题解：P3381 【模板】最小费用最大流

ffengzhaoyu
P3381题解参与者 6已保存评论 8

文章操作

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

当前评论
8 条
当前快照
1 份
快照标识符
@mioxlv7c
此快照首次捕获于
2025/12/03 02:48
3 个月前
此快照最后确认于
2025/12/03 02:48
3 个月前
查看原文
原始对偶算法是个好东西

思路

前置芝士：dinic-算法。
看看题解没有 dijkstra 加 dinic 的，这里来写一下。
首先要知道，网络流就是对于一条 u→vu\rightarrow v 的路径反向再建权值为 0 的路径，如果这条路经过了 xx 的流量，那么他的反边就会增加 xx 的权值，以便以后可以“反悔”。最小费用最大流是贪心地每次按价格的最短路进行增广，那很容易想到加一个 spfa，每次都找一条 s→ts\rightarrow t 的最短路进行增广，直到不存在这样的路径为止。可以证明，此时的路径一定最优（蒟蒻太蒟蒻了，不会证，有意愿者可以上网查证明方法），详见代码。
CPP
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N=5e4+15,M=5e5+15,inf=INT_MAX;
int read()
{
	int t=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') t=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return t*x;
}
int cur[N],to[M],ne[M],f[M],w[M],d[N],vis[N];
int dis[N],hh[N];
int n,m,s,t,idx;
void add(int u,int v,int ww,int c)
{
	to[idx]=v;
	ne[idx]=hh[u];
	f[idx]=ww;// 流量限制
	w[idx]=c;// 价格
	hh[u]=idx++;
}
bool spfa()//求最短路并判断此时是否存在增广路
{
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++) dis[i]=inf;
	queue<int>q;
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	d[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=hh[u];i!=-1;i=ne[i])
		{
			int v=to[i];
			if(f[i]&&dis[v]>dis[u]+w[i])
			{
				dis[v]=dis[u]+w[i];
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	if(dis[t]<inf) return 1;
	return 0;
}
int ans1=0,ans2=0;
int dfs(int u,int mf)
{
	if(u==t) return mf;
	int sum=0;
	vis[u]=1;//这样是为了下文判断是否存在负环，如果有，可直接跳过
	for(int i=cur[u];i!=-1;i=ne[i])
	{
		cur[u]=i;//当前弧优化
		int v=to[i];
		if(f[i]&&dis[v]==dis[u]+w[i]&&vis[v]==0)//保证了一定会按最短路增广
		{
			int ff=dfs(v,min(mf,f[i]));
			f[i]-=ff;
			f[i^1]+=ff;
			sum+=ff;
			mf-=ff;
			ans2+=ff*w[i];//由于dinic是多路增广，所以只能边遍历便更新值
			if(mf==0) break;
		}
	}
	vis[u]=0;
//	if(sum==0) d[u]=0;
	return sum;
}
void Dinic()
{
	while(spfa())
	{
		memcpy(cur,hh,sizeof hh);
		ans1+=dfs(s,inf);
	}
	printf("%d %d\n",ans1,ans2);
}
int main()
{
	memset(hh,-1,sizeof hh);
	n=read(),m=read(),s=read(),t=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read(),c=read();
		add(u,v,w,c);
		add(v,u,0,-c);
	}
	Dinic();
	return 0;
}
但是，我们知道，关于 spfa，它已经死了远不如 dijkstra，那有没有一种方法使此题能用 dijkstra 呢？有，原始对偶算法。我们先想，此题本来不用 dijkstra 的原因是因为有负环，那我们是否能变负为正呢？
  1. 引入势函数（对偶变量）huh_{u}，为每个节点 vv 维护一个势能值。
  2. 重新定义边权：对每条边 u→vu\rightarrow v，定义修正边权：cu,v′=cu,v+hu−hvc'_{u,v}=c_{u,v}+h_u−h_v。
  3. 其中 cu,vc_{u,v} 是原始费用。可以通过设置合适的 huh_u，使得所有修正权 cu,v′≥0c'_{u,v}\geq 0，从而允许使用 dijkstra 算法。
  4. 那么由此可得：cu,v+hu−hv≥0c_{u,v}+h_u-h_v\geq 0，将 hvh_v 移项——不就是最短路中的松弛操作吗？那好，初始势函数的值可以用从 ss 出发的最短路来表示。(正确性的证明：对于一条增广路，一条边 ci,j′=ci,j+hi−hjc'_{i,j}=c_{i,j}+h_i-h_j，它的下一条边 cj,k′=cj,k+hj−hkc'_{j,k}=c_{j,k}+h_j-h_k，当它们相加时，hjh_j 抵消了！由此推出：∑cu,v′=∑cu,v+hs−ht\sum c'_{u,v}=\sum c_{u,v}+h_s-h_t，因此，路径的实际费用与修正费用仅相差一个常数，与路径无关。也就是说，每次增广多带来的值是一样的。)
  5. 设 d_{v} 是当前残量网络中从 ss 到 vv 的最短修正距离（dijkstra 得），势函数更新为 hnewv=holdv+dvh_{newv}=h_{oldv}+d_{v}。此时是否仍然保持非负性？对于一条边，dv≤du+cu,v′=du+cu,v+holdu−holdvd_v\leq d_{u}+c'_{u,v}=d_u+c_{u,v}+h_{oldu}-h_{oldv}，整理得：cu,v+holdu+du−holdv+dv≥0c_{u,v}+h_{oldu}+d_u-h_{oldv}+d_v\geq 0，其中 holdu+du−holdvh_{oldu}+d_u-h_{oldv} 就是势函数更新了。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N=1e5+15,inf=INT_MAX;
int read()
{
	int t=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') t=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return t*x;
}
int cur[N],to[N],ne[N],f[N],w[N],vis[N];
int dis[N],h[N],hh[N];
int n,m,s,t,idx;
void add(int u,int v,int ww,int c)
{
	to[idx]=v;
	ne[idx]=hh[u];
	f[idx]=ww;
	w[idx]=c;
	hh[u]=idx++;
}
void spfa()//求h初始值，因为只跑一次，所以不会慢
{
	memset(h,0x3f,sizeof h);
	queue<int>q;
	q.push(s);
	vis[s]=1;
	h[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=hh[u];i!=-1;i=ne[i])
		{
			int v=to[i];
			if(f[i]&&h[v]>h[u]+w[i])
			{
				h[v]=h[u]+w[i];
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}

}
bool dijkstra()
{
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++) dis[i]=inf;
	priority_queue<pii,vector<pii>,greater<pii> >q;
	q.push({0,s});
	dis[s]=0;
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=hh[u];i!=-1;i=ne[i])
		{
			int v=to[i];
			if(f[i]&&dis[v]>dis[u]+w[i]+h[u]-h[v])
			{
				
				dis[v]=dis[u]+w[i]+h[u]-h[v];
				q.push({dis[v],v});
			}
		}
	}
	return dis[t]!=inf;
}
int ans1=0,ans2=0;
int dfs(int u,int mf)
{
	if(u==t) return mf;
	int sum=0;
	vis[u]=1;
	for(int i=cur[u];i!=-1;i=ne[i])
	{
		cur[u]=i;
		int v=to[i];
		if(f[i]&&vis[v]==0&&h[v]==h[u]+w[i])
		{
			
//			cout<<"ll";
			int ff=dfs(v,min(mf,f[i]));
			f[i]-=ff;
			f[i^1]+=ff;
			sum+=ff;
			mf-=ff;
			ans2+=ff*w[i];
			if(mf==0) break;
		}
	}
	vis[u]=0;
	return sum;
}
void Dinic()
{
	spfa();
	while(dijkstra())
	{
		memset(vis,0,sizeof vis);
		memcpy(cur,hh,sizeof hh);
		for(int i=1;i<=n;i++) h[i]+=dis[i];
		int k=dfs(s,inf);
		ans1+=k;
	}
	printf("%d %d\n",ans1,ans2);
}
int main()
{
	memset(hh,-1,sizeof hh);
	n=read(),m=read(),s=read(),t=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read(),c=read();
		add(u,v,w,c);
		add(v,u,0,-c);
	}
	Dinic();
	return 0;
}
完美撒花！

评论

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

正在加载评论...