网络流学习笔记——最小费用最大流

想象这样一个场面：从自来水厂到你家有若干根水管，每根水管都有一个流量上限，还有一个单位流量的费用。

你现在不仅想要让流到你家的水尽量多，还想尽可能节省费用。这就是最小费用最大流问题了。

Part 1 EK+SPFA

每次增广过程时，每条边增广的流量是一样的，所以我们只需要让每次增广的费用尽可能小就可以了。

问题就转化成了从 \(S\) 到 \(T\) 的最短路。

因为有费用为负的边（反边的费用要和正边互为相反数），所以我们考虑用 SPFA 来求最短路。

将 EK 中的 BFS 改成 SPFA 就解决问题了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,f,next;
}e[100005];
struct node
{
 int v,e;
}p[10005];
int head[5005],dist[5005],vis[5005];
int n,m,s,t,cnt=1,maxw,minf;
void addedge(int u,int v,int w,int f)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].f=f;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool spfa()
{
 queue<int> q;
 memset(dist,INF,sizeof(dist));
 q.push(s);
 dist[s]=0;
 vis[s]=1;
 while(!q.empty())
 {
  int cur=q.front();
  q.pop();
  vis[cur]=0;
  for(int i=head[cur];i;i=e[i].next)
   if(e[i].w&&dist[cur]+e[i].f<dist[e[i].v])
   {
    dist[e[i].v]=dist[cur]+e[i].f;
    p[e[i].v].v=cur;
    p[e[i].v].e=i;
    if(!vis[e[i].v])
    {
     vis[e[i].v]=1;
     q.push(e[i].v);
    }
   }
 }
 return dist[t]!=INF;
}
int main()
{
 scanf("%d%d%d%d",&n,&m,&s,&t);
 for(int i=1;i<=m;i++)
 {
  int u,v,w,f;
  scanf("%d%d%d%d",&u,&v,&w,&f);
  addedge(u,v,w,f);
  addedge(v,u,0,-f);
 }
 while(spfa())
 {
  int minw=INF;
  for(int i=t;i!=s;i=p[i].v)
   minw=min(minw,e[p[i].e].w);
  for(int i=t;i!=s;i=p[i].v)
  {
   e[p[i].e].w-=minw;
   e[p[i].e^1].w+=minw;
  }
  maxw+=minw;
  minf+=minw*dist[t];
 }
 printf("%d %d\n",maxw,minf);
 return 0;
}