什么是最小费用最大流

• 一个网络，每个边除了流量，还有一个单位费用，这条边的费用相当于它的单位费用乘上它的流量，我们要保持最大流的同时，还要保持边权最小，这就是最小费用最大流问题。
• 在一个网络流图中，最大流量只有一个，但是获得最大流的方案可能有很多种，每种不同的方案所经过的边不同因此费用也就不同，所以需要用到最短路算法。
• 总增广的费用=最短路费用*总流量
• 求MCMF中的算法

1. 基于EK:把EK中的bfs改成spfa,这样在求最大流的过程中最小费用流也求出来了。
2. 基于Dinic: 也是把Dinic中的bfs改成spfa，保证单位流量费用的最短路，可参考一下这里

P3381 【模板】最小费用最大流

1. EK+SPFA

#include<stdio.h>#include<queue>#include<string.h>#include<algorithm>using namespace std;typedef long long ll;ll const N=100010;ll const M=100010;ll const INF=0x7f;ll n,m,s,t,pre[N],dis[N],last[N],flow[N],vis[N],maxflow,mincost;ll cnt,head[N];struct edge{ll to,next,cap,dis;}e[M];queue<ll> q;void add(ll u,ll v,ll cap,ll dis){cnt++;e[cnt].to=v;e[cnt].next=head[u];e[cnt].cap=cap;e[cnt].dis=dis;head[u]=cnt;}bool spfa(ll s,ll t){memset(dis,INF,sizeof(dis));memset(flow,INF,sizeof(flow));memset(vis,0,sizeof(vis));q.push(s);dis[s]=0;vis[s]=1;pre[t]=-1;while(q.size()){ll now=q.front();q.pop();vis[now]=0;for(ll i=head[now];i!=-1;i=e[i].next){ll v=e[i].to;if(dis[v]>dis[now]+e[i].dis&&e[i].cap>0){dis[v]=dis[now]+e[i].dis;pre[v]=now;last[v]=i;flow[v]=min(flow[now],e[i].cap);if(!vis[v]){vis[v]=1;q.push(v);}}}}return pre[t]!=-1;}void EK(){while(spfa(s,t)){ll now=t;maxflow+=flow[t];mincost+=flow[t]*dis[t];while(now!=s){e[last[now]].cap-=flow[t];e[last[now]^1].cap+=flow[t];now=pre[now];}}}int main(){memset(head,-1,sizeof(head));cnt=-1;scanf(\"%lld%lld%lld%lld\",&n,&m,&s,&t);ll u,v,c,w;for(ll i=1;i<=m;i++){scanf(\"%lld%lld%lld%lld\",&u,&v,&c,&w);add(u,v,c,w);add(v,u,0,-w);//反边}EK();printf(\"%lld %lld\\n\",maxflow,mincost);return 0;}

1. Dinic+SPFA

#include<stdio.h>#include<queue>#include<string.h>#include<algorithm>using namespace std;const int N=5e3+10,M=5e4+10,INF=0x7f7f7f7f;int n,m,s,t,mincost;int cnt,head[N],cur[N],dis[N],vis[N];struct edge{int to,next,cap,cost;}e[M<<1];void add(int u,int v,int cap,int cost){e[cnt].to=v;e[cnt].next=head[u];e[cnt].cap=cap;e[cnt].cost=cost;head[u]=cnt;cnt++;}bool spfa(){memset(dis,INF,sizeof(dis));memset(vis,0,sizeof(vis));queue<int> q;q.push(s);dis[s]=0;vis[s]=1;while(q.size()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(e[i].cap>0&&dis[u]+e[i].cost<dis[v]){dis[v]=dis[u]+e[i].cost;if(!vis[v]){vis[v]=1;q.push(v);}}}}if(dis[t]!=INF)return 1;return 0;}int dfs(int u,int flow){vis[u]=1;if(u==t)return flow;for(int i=cur[u];i!=-1;i=e[i].next){cur[u]=i;int v=e[i].to;if(e[i].cap>0&&dis[u]+e[i].cost==dis[v]&&!vis[v]){int delta=dfs(v,min(e[i].cap,flow));if(delta>0){e[i].cap-=delta;e[i^1].cap+=delta;mincost+=delta*e[i].cost;return delta;}}}vis[u]=0;return 0;}int getmaxflow(){int maxflow=0,delta;while(spfa()){//memcpy(cur,head,sizeof(head));for(int i=0;i<=n;i++)cur[i]=head[i];while(delta=dfs(s,INF))maxflow+=delta;}return maxflow;}int main(){scanf(\"%d%d%d%d\",&n,&m,&s,&t);int u,w,v,f;memset(head,-1,sizeof(head));for(int i=1;i<=m;i++){scanf(\"%d%d%d%d\",&u,&v,&w,&f);add(u,v,w,f);add(v,u,0,-f);//反边}int maxflow=getmaxflow();printf(\"%d %d\\n\",maxflow,mincost);return 0;}