本文共 4009 字，大约阅读时间需要 13 分钟。

最小费用最大流

$如果你会最大流,那这个基本上可以秒懂。$

$问题描述$

$给出一个网络图，以及其源点s和汇点t$

可以发现相比最大流多了一个单位流量费用的限制

$那找怎样的路径比较合理?$

$把单位费用看作边的权值,从源点到汇点跑最短路$

$每次找一条s到t的花费最小的路径,同时记录路径和路上的最小流量$

$如果汇点的最短路被更新,说明找到路径,完成了bfs判断是否有路径的功能$

而且$通过记录走到汇点的路径,可以直接对路径上边的流量做修改$

$如此一来,不停的利用spfa找最短路即可$

$最小费用最大流(spfa版本)就是这样一种算法$

#include 
   
    using namespace std;const int maxn=50009;const int inf=1e9;int n,m,s,t;int maxflow,mincost;int dis[maxn],head[maxn<<1],cnt=1,incf[maxn],pre[maxn],vis[maxn];struct EDGE{	int to,nxt,w,flow;//分别代表 }d[maxn<<1];void add(int u,int v,int flow,int w)//flow最大流量,w单位费用{	d[++cnt].to=v,d[cnt].flow=flow,d[cnt].w=w,d[cnt].nxt=head[u],head[u]=cnt;	} bool spfa(){	queue
    
     q;	for(int i=0;i<=n;i++)	dis[i]=inf;	memset(vis,0,sizeof(vis));	q.push(s);	dis[s]=0,vis[s]=1;	incf[s] = inf;//初始流量无限大	while( !q.empty() )	{		int u=q.front(); q.pop();		vis[u]=0;//出队		for(int i=head[u];i;i=d[i].nxt)		{			if( !d[i].flow )	continue;//无流量了				int v=d[i].to;			if( dis[v]>dis[u]+d[i].w )			{				dis[v]=dis[u]+d[i].w;				incf[v] = min(incf[u],d[i].flow);//更新当前流量				pre[v]=i;//记录从哪条边过来的				if( !vis[v] )	vis[v]=1,q.push(v); 			}		}		} 	if( dis[t]==inf )	return 0;	return 1;}void dinic(){	while( spfa() )	{		int x=t;//倒回去找路径		maxflow+=incf[t];		mincost+=dis[t]*incf[t];		int i;		while(x != s)		{			i=pre[x];			d[i].flow-=incf[t];//减去流量			d[i^1].flow+=incf[t];//加上流量			x = d[i^1].to;//因为是倒回去,所以利用反向边倒回去 		 } 	}}int main(){	cin >> n >> m >> s >> t;	for(int i=1;i<=m;i++)	{		int l,r,w,x;		cin >> l >> r >> w >> x;		add(l,r,w,x); add(r,l,0,-x);	}	dinic();	cout << maxflow << " " << mincost;}
    
   

下面是最大费用最大流,就是建边的时候把边权取反就行,输出再次取反

#include 
   
    using namespace std;const int maxn=50009;const int inf=1e9;int n,m,s,t,a[59][59];int maxflow,mincost;int dis[maxn],head[maxn<<1],cnt=1,incf[maxn],pre[maxn],vis[maxn];struct EDGE{
   	int to,nxt,w,flow;//分别代表 }d[maxn<<1];void add(int u,int v,int flow,int w)//flow最大流量,w单位费用{
   	d[++cnt].to=v,d[cnt].flow=flow,d[cnt].w=w,d[cnt].nxt=head[u],head[u]=cnt;	d[++cnt].to=u,d[cnt].flow=0,d[cnt].w=-w,d[cnt].nxt=head[v],head[v]=cnt;	} bool spfa(){
   	queue
    
     q;	for(int i=0;i<=t;i++)	dis[i]=inf;	memset(vis,0,sizeof(vis));	q.push(s);	dis[s]=0,vis[s]=1;	incf[s] = inf;//初始流量无限大	while( !q.empty() )	{
   		int u=q.front(); q.pop();		vis[u]=0;//出队		for(int i=head[u];i;i=d[i].nxt)		{
   			if( !d[i].flow )	continue;//无流量了				int v=d[i].to;			if( dis[v]>dis[u]+d[i].w )			{
   				dis[v]=dis[u]+d[i].w;				incf[v] = min(incf[u],d[i].flow);//更新当前流量				pre[v]=i;//记录从哪条边过来的				if( !vis[v] )	vis[v]=1,q.push(v); 			}		}		} 	if( dis[t]==inf )	return 0;	return 1;}void dinic(){
   	while( spfa() )	{
   		int x=t;//倒回去找路径		maxflow+=incf[t];		mincost+=dis[t]*incf[t];		int i;		while(x != s)		{
   			i=pre[x];			d[i].flow-=incf[t];//减去流量			d[i^1].flow+=incf[t];//加上流量			x = d[i^1].to;//因为是倒回去,所以利用反向边倒回去 		 } 	}}int main(){
   	cin >> n >> m;	s=0,t=n*n*2+1;	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	cin >> a[i][j];	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	{
   		int x=(i-1)*n+j,y=i*n+j;		if( i!=n )	add(x+n*n,y,inf,0);		if( j!=n )	add(x+n*n,x+1,inf,0);		add(x,x+n*n,1,-a[i][j]);		add(x,x+n*n,inf,0);	}	add(s,1,m,0);	add(n*n*2,t,m,0);	dinic();	cout << -mincost;}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107326691 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！