好惧怕这个233，一直就搞不懂，今天还是被迫去搞了，下午讲课从费用流就开始基本懵
首先最小费用最大流是指，在取得最大流的情况下，可能有多种方式，然而现在引入一个变量费用，也就是每一条边流过一单位流量的价格，现在要求总的费用在取得最大流的情况下最小
大概就是这么个意思，那么我们进行求解呢？ 有一点是无疑的，无论有没有费用这个量，我们求出的最大流是一样的，所以我们可以在每次增广的时候选取一条最短路进行增广，什么叫最短路呢？（…当然大家都知道怎么搞最短路…我的意思是…为什么是最短路呢…）
我们可以这样理解
例子是刘汝佳的图，a表示单位流量费用，c表示容量…我为什么把点画得这么大…感觉好丑… 所以这样的一张有向图，我们可以这样进行增广：在增广的同时找最短路 以a为路的长度进行最短路，第一次显然可以这样地增广一条路
这样一条路是当前可以增广最大的最大流量，并且这样一条路的a值和是最小的，因此这样一条流量从S到T的费用就是流量乘以a值的和最小，这条路增广之后还可以增广S-X-T这条路，至此，最小费用最大流的求解思路就讲解完毕，下面附上代码，用SPFA实现最短路求解（支持国产233）
模板大概就是这么个样子，P.s 该模板建图少了一部分，因为具体题目具体建图
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #define MAXN 10000+10 using namespace std; int tail=-1,head[MAXN],s=0,t,dis[MAXN],pre[MAXN],N,M,flow,fee; bool vis[MAXN]; struct Line{ int to,nxt,flow,fee; }line[MAXN]; void init(){ memset(head,0,sizeof(head)); tail=-1; } void add_line(int from,int to,int flow,int fee){ tail++; line[tail].to=to; line[tail].flow=flow; line[tail].fee=fee; line[tail].nxt=head[from]; head[from]=tail; } bool SPFA(int s,int t){ queue<int>q; q.push(s); memset(dis,0x7fff,sizeof(dis)); memset(vis,false,sizeof(vis)); memset(pre,0,sizeof(pre)); vis[s]=true; dis[s]=0; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=line[i].nxt){ int v=line[i].to; if(line[i].flow>0&&dis[v]>dis[u]+line[i].fee){ dis[v]=dis[u]+line[i].fee; pre[v]=i;//录入的是边的编号 if(!vis[v]){ vis[v]=true; q.push(v); } } } } if(pre[t]==0) return false; else return true; } void MCMF(int s,int t,int flow,int fee){ flow=fee=0; while(SPFA(s,t)){ int minn=0x7fffffff; for(int i=pre[t];i;i=pre[i]){ int f=line[i].flow; minn=min(minn,f); } for(int i=pre[t];i;i=pre[i]){ line[i].flow-=minn; line[i^1].flow+=minn; fee+=line[i].fee*minn; } flow+=minn; } } int main(){ while(scanf("%d%d",&N,&M),N||M){ init();t=N+1; for(int i=1;i<=M;i++){ int from,to,flow,fee; scanf("%d%d%d%d",&from,&to,&flow,&fee); add_line(from,to,flow,fee); add_line(to,from,0,-fee); } //此处是其他的连边,因为具体题目连的方式不同 MCMF(s,t,flow,fee); printf("%d%d",flow,fee); } return 0; }