想象这样一个场面:从自来水厂到你家有若干根水管,每根水管都有一个流量上限,还有一个单位流量的费用。
你现在不仅想要让流到你家的水尽量多,还想尽可能节省费用。这就是最小费用最大流问题了。
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; }