给出一个容量网络，那他的最大流一定是一个定值（即使是有多个一样的最大值）。
所以我们从开始的可行流开始增广时，最终的增广量是一定的。 所以为了满足最小费用我们只需要每次找最小费用的增广路即可，直到流量为最大值。 这个问题仅仅是在求增广路时先考虑费用最小的增广路，其他思想和EK思想一样。 我们学过SPFA求最短路算法（bellman-ford的队列优化），所以我们将弧的费用看做是路径长度，即可转化为求最短路的问题了。只需要所走的最短路满足两个条件即可：1剩余流量不为0,2路径变短d[v]>d[u]+cost< u,v> 。
#include#include #include #include #include #include #include using namespace std;int n,m,S,T;int num[100005],cap[100005],cost[100005],nxt[100005],head[5005],cnt=1;//cap记残余流量，cost记费用int dis[5005],flow[5005],xb[5005];//xb记链表数组的下标，dis用于spfaint pre[5005];bool used[5005];int mflow=0,mcost=0;void add(int from,int to,int ca,int co){ cnt++;//从 2 开始 ,若从0开始，会导致找点时循环停止！！！ num[cnt]=to; nxt[cnt]=head[from]; head[from]=cnt; cost[cnt]=co; cap[cnt]=ca;}int bfs(int s,int t){ memset(dis,127,sizeof(dis)); memset(used,false,sizeof(used)); for(int i=1;i<=n;i++) pre[i]=-1; queue q; while(!q.empty()) q.pop(); q.push(s); pre[s]=0; dis[s]=0; used[s]=true; flow[s]=dis[0]; while(!q.empty()) { int k=q.front(); q.pop(); used[k]=false; for(int i=head[k];i;i=nxt[i]) { int to=num[i]; if(cap[i]>0&&dis[to]>dis[k]+cost[i])//在spfa判断条件基础上，加上剩余流量>0 { xb[to]=i; dis[to]=dis[k]+cost[i]; flow[to]=min(flow[k],cap[i]); if(!used[to]) used[to]=true,q.push(to); pre[to]=k; } } } if(pre[t]==-1) return -1; else return flow[t]; }void maxflow(int s,int t){ int d; while(bfs(s,t)!=-1) { d=flow[t]; int k=t; while(k!=s) { cap[xb[k]]-=d; cap[xb[k]^1]+=d; k=pre[k]; } mflow+=d; mcost+=d*dis[t];//每条边上的流量为d，dis[t]为每条边单位流量费用之和 if(d==0) break; } return;}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); add(u,v,w,f); add(v,u,0,-f); } maxflow(S,T); printf("%d %d",mflow,mcost); return 0;}