2023年7月30日发(作者：)

最⼩费⽤最⼤流代码模板及注释代码来⾃刘汝佳紫书上的代码，最⼤流使⽤EK算法，最短路径使⽤算法为SPFA。解释：继承寻找最⼤流算法的思路，在⼀个⽹络当中，最⼤流的值是唯⼀的，但是路径可以有不同，寻找最⼤流的算法是每次从起点寻找⼀条到终点的增⼴路径，每次把这条路径经过的边都添加增⼴路径找到的流量，然后更改每条边上的流量以及反向变的值，直到找不到这样⼀条增⼴路径，就算是找完最⼤流了。之前找增⼴路径的⽅法是随机找的，如果是最⼩费⽤，我们就把费⽤看做边上的另外⼀个权值，以这个权值按照最短路径的⽅式去找增⼴路径。最后得到最⼤流的同时也得到了最⼩的费⽤。const int maxn=10001;struct Edge//边{ int from,to,cap,flow,cost;//出点，⼊点，容量，当前流量，费⽤（也就是权值） Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}};struct MCMF{ int n,m; vector edges;//保存表 vector G[maxn];//保存邻接关系 int inq[maxn];//判断⼀个点是否在队列当中（SPFA算法当中要⽤） int d[maxn];//起点到d[i]的最短路径保存值 int p[maxn];//⽤来记录路径，保存上⼀条弧 int a[maxn];//找到增⼴路径后的改进量 void init(int n)//初始化 { this->n=n; for(int i=0;i<=n;i++) G[i].clear(); (); } void AddEdge(int from,int to,int cap,int cost)//添加边 { _back(Edge(from,to,cap,0,cost));//正向 _back(Edge(to,from,0,0,-cost));//反向 m=(); G[from].push_back(m-2);//按照边的编号保存邻接关系 G[to].push_back(m-1); } bool BellmanFord(int s,int t,int& flow,long long& cost)//最短路径算法 { for(int i=0;i<=n;i++) d[i]=INT_MAX; memset(inq,0,sizeof(inq)); d[s]=0; inq[s]=1; p[s]=0; a[s]=INT_MAX; queue Q; (s); while(!()) { int u=(); (); inq[u]=0; for(int i=0;i&&d[]>d[u]+)//寻找满⾜容量⼤于流量的可松弛边 { d[]=d[u]+; p[]=G[u][i]; a[]=min(a[u],); if(!inq[])//是否在队列当中 { (); inq[]=1; } } } } if(d[t]==INT_MAX)//如果d[t]没有被更新，相当于没找到增⼴路径，则没有最⼤流也没有最⼩费⽤ return false; flow+=a[t];//更新最⼤流 cost+=(long long )d[t]*(long long)a[t];//单位流量乘以单位路径长度⽤来计算消耗 for(int u=t;u!=s;u=edges[p[u]].from)//通过使⽤p[]保存的上⼀个边的值来对刚刚找到的增⼴路径上⾯的流量进⾏更新 { edges[p[u]].flow+=a[t];//正向变更新 edges[p[u]^1].flow-=a[t];//反向变更新（⽤位运算实现的） } return true; } int MincostMaxflow(int s,int t,long long& cost)//计算从s到t的最⼩消耗cost，返回最⼤流 { int flow = 0; cost=0; while(BellmanFord(s,t,flow,cost));//不断寻找最短增⼴路径，直到找不到为⽌ return flow; }};