学习了网络流最基本的最大流算法以后，当然就会有更进一步的问题，那就是最小费用最大流。
顾名思义，最小费用最大流就是在原本的有向图中，单位流量加入费用，并在原本最大流的基础上找到一个费用最小的最大流。
很明显，在一个网络中最大流可能有多种流法（懂那个意思就行了，听着别扭就算了啊，不要紧的纠结要不要得？），所以在原本最大流的基础上，运用Spfa或者其他方法进行类似最短路的算法就可以找到最小费用最大流，，，具体还是看代码吧（我实在是太懒了_(:з」∠)_）：
这里是洛谷的模板题：
#include<cstdio> #include<queue> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #define inf 1e9 using namespace std; const int N=5050; const int M=50050; deque<int>Q; int n,m,start,endd; int dis[N],ans,res; int head[N],size=1; bool vis[N],inq[N]; struct Node{ int to,val,cost,next; }edge[M<<1]; inline int read() { char ch=getchar();int num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();} while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } inline void add(int x,int y,int z,int c) { edge[++size].to=y; edge[size].val=z; edge[size].cost=c; edge[size].next=head[x]; head[x]=size; } inline void add_edge(int x,int y,int z,int c) {add(x,y,z,c);add(y,x,0,-c);} void ready() { memset(head,-1,sizeof(head)); n=read();m=read(); start=read();endd=read(); for(int i=1;i<=m;i++){ int x=read();int y=read(); int z=read();int c=read(); add_edge(x,y,z,c); } } inline bool bfs() { for(int i=0;i<=n;i++)dis[i]=inf; memset(inq,false,sizeof(inq)); dis[endd]=0;inq[endd]=true; Q.push_back(endd); while(!Q.empty()){ int x=Q.front();Q.pop_front(); inq[x]=false; for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(edge[i^1].val&&dis[y]>dis[x]-edge[i].cost){ dis[y]=dis[x]-edge[i].cost; if(!inq[y]){inq[y]=true; if(Q.empty()||dis[y]>=dis[Q.front()])Q.push_back(y); else Q.push_front(y); } } } } return dis[start]<dis[0]; } inline int dfs(int u,int flow) { vis[u]=true; if(u==endd||flow==0)return flow; int used=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!vis[v]&&edge[i].val&&dis[v]==dis[u]-edge[i].cost){ int ka=flow-used; ka=dfs(v,min(edge[i].val,ka)); edge[i].val-=ka; edge[i^1].val+=ka; used+=ka; if(used==flow)return used; } } return used; } void work() { while(bfs()){ vis[endd]=true; while(vis[endd]){ memset(vis,false,sizeof(vis)); int flow=dfs(start,inf); res+=flow*dis[start]; ans+=flow; } } printf("%d %d",ans,res); } int main() { ready(); work(); return 0; }
这里BFS的时候使用了双端队列，实际上不用也可以，但是用的话会快不少，据我实测，使用双端队列最慢的点388ms，不用双端队列最慢的点600ms
差距貌似挺大的。。。囧。。。不过一般情况下不用也是没问题的（除非出题人丧心病狂到卡这种数据。。。）