本文非原创，大部分参考自秋日私语大大的题解。
GO：模板
最大流问题，我们可以通过EK，DINIC等方法解决，但是如果在每条边上加上边权，并定义 费用 为边权乘以流量，在所有最大流中求出费用最少的那一个方案，就需要新的算法了。
这里只对最小费用最大流的EK-SPFA算法做一些自己的解释，并会附上模板。
首先是EK算法：
1.我们每次求一条源点到汇点的路径，流量最大为路径上的最小流量minflow，所以下一次寻找最大流就不能走那条，于是将所有边的流量减小minflow。
2.由1能保证求出最大流吗？答案是否定的，因为当我们遇到一些特殊的图时：
比如这个，第一条路径S-2-T，边上流量变为0，得到maxflow=4，实际上maxflow=6，因此我们要加一条反向边让路径有“反悔”的机会。
3.我们使用bfs进行增广，这样能保证在更少的次数下求出最大流。
4.对2具体的操作：记录路径上每个点的前驱和前驱边，走完spfa后从后向前遍历前驱边，修改流量。
最小费用最大流：
众所周知，SPFA他死了。
但这并不影响我们做网络流的题目（出题人没必要在网络流的题目上用图论卡我们），我们借鉴spfa的思想，对路径上求最短路。
具体看代码。
1 //EK-MCMF 2 #include<bits/stdc++.h> 3 using namespace std; 4 const int inf=1e9; 5 #define f(i,a,b) for(register int i=a;i<=b;i++) 6 const int N=5e4+10; 7 int head[N<<1],flow[N],l[N],dis[N],pre[N],vis[N],cnt=-1,n,m,s,t,ansf,ansc; 8 //flow判断路径最小流量，dis判断最短路，pre是前驱点，l是前驱边，vis判断是否在队列中 9 queue<int> q; 10 struct edge{int to,next,f,w;}e[N<<1]; 11 void addedge(int from,int to,int f,int w){e[++cnt]=(edge){to,head[from],f,w}; head[from]=cnt;} 12 bool spfa(){ 13 memset(dis,0x7f,sizeof(dis)); 14 memset(vis,0,sizeof(vis)); 15 vis[s]=1; 16 dis[s]=pre[t]=0; 17 flow[s]=inf; 18 q.push(s); 19 while(!q.empty()){ 20 int u=q.front(); 21 vis[u]=0; 22 for(int i=head[u];i!=-1;i=e[i].next){ 23 int v=e[i].to,w=e[i].w,f=e[i].f; 24 if(f>0&&dis[v]>dis[u]+w){ 25 dis[v]=dis[u]+w; 26 pre[v]=u; 27 l[v]=i; 28 flow[v]=min(flow[u],f); 29 if(!vis[v]){ 30 q.push(v); 31 vis[v]=1; 32 } 33 } 34 } 35 q.pop(); 36 } 37 return pre[t]; 38 } 39 void solve(){ 40 while(spfa()){ 41 ansf+=flow[t]; 42 ansc+=dis[t]*flow[t]; 43 for(int i=t;i!=s;i=pre[i]){ 44 int edge_=l[i]; 45 e[edge_].f-=flow[t]; 46 e[edge_^1].f+=flow[t]; 47 } 48 } 49 printf("%d %d",ansf,ansc); 50 } 51 int main(){ 52 memset(head,-1,sizeof(head)); 53 scanf("%d%d%d%d",&n,&m,&s,&t); 54 int x,y,f,w; 55 f(i,1,m){ 56 scanf("%d%d%d%d",&x,&y,&f,&w); 57 addedge(x,y,f,w); 58 addedge(y,x,0,-w); 59 } 60 solve(); 61 return 0; 62 }
原文：https://www.cnblogs.com/Nelson992770019/p/11336039.html