给出一个容量网络，那他的最大流一定是一个定值（即使是有多个一样的最大值）。所以我们从开始的可行流开始增广时，最终的增广量是一定的。所以为了满足最小费用我们只需要每次找最小费用的增广路即可，直到流量为最大值。这个问题仅仅是在求增广路时先考虑费用最小的增广路，其他思想和EK思想一样。 我们学过SPFA求最短路算法（bellman-ford的队列优化），所以我们将弧的费用看做是路径长度，即可转化为求最短路的问题了。只需要所走的最短路满足两个条件即可：1可增广cap> flow,2路径变短d[v]>d[u]+cost< u,v>
网络流（六）最小费用最大流问题
其实就是把dinic中的bfs换成spfa,dfs换成回溯修改剩余网络和答案的过程。
算法流程：
用spfa寻找每条边上费用之和最小的增广路，沿途找到最小流量，把经过的点记录下来。把最小费用增广路上的边剩余流量修改了回到1注意，反边费用为其对应边的相反数
ps:有个很神奇的地方没搞懂：一开始我忘记打spfa里面“bz[x]=0;”这一句，结果算出的最大流比答案大？！！
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct qy { int x,y,flow,cost; }; int n,m,S,T,i,j,x,y,z1,z2,tot,maxflow,mincost; qy l[200005]; int next[200005],last[200005]; int dis[5005],flow[5005],from[5005],bz[5005]; int list[200005],head,tail; void insert(int x,int y,int z1,int z2) { tot++; l[tot].x=x; l[tot].y=y; l[tot].flow=z1; l[tot].cost=z2; next[tot]=last[x]; last[x]=tot; } int spfa() { memset(bz,0,sizeof(bz)); memset(flow,0,sizeof(flow)); memset(dis,120,sizeof(dis)); list[1]=S;bz[S]=1;head=0;tail=1;dis[S]=0;flow[S]=1000000000; while (head<tail) { int x=list[++head]; for (int i=last[x];i>=1;i=next[i]) { int y=l[i].y; if ((l[i].flow>0)&&(dis[y]>dis[x]+l[i].cost)) { dis[y]=dis[x]+l[i].cost; from[y]=i; flow[y]=min(flow[x],l[i].flow); if (!bz[y]) { bz[y]=1;list[++tail]=y; } } } bz[x]=0; } if (flow[T]>0) return 1; else return 0; } void mfmc() { while (spfa()) { maxflow+=flow[T]; mincost+=flow[T]*dis[T]; for (int x=T;x!=S;x=l[from[x]].x) { l[from[x]].flow-=flow[T]; l[from[x]^1].flow+=flow[T]; } } } int main() { freopen("read.in","r",stdin); scanf("%d%d%d%d",&n,&m,&S,&T); tot=1; for (i=1;i<=m;i++) { scanf("%d%d%d%d",&x,&y,&z1,&z2); insert(x,y,z1,z2); insert(y,x,0,-z2); } mfmc(); printf("%d %d",maxflow,mincost); }转载于:https://www.cnblogs.com/leason-lyx/p/11147261.html
相关资源：数据结构—成绩单生成器