本文共 4225 字，大约阅读时间需要 14 分钟。

最小费用最大流算法

代码实现

/*参考:《趣学算法》陈小玉 人民邮电出版社最小费用最大流---最小费用路算法问题分析:    在实际应用中，要同时考虑流量和费用，每条边除了给定容量之外，    还定义了一个单位流量的费用.    网络流的费用=每条边的流量*单位流量费用    我们希望费用最小，流量最大，因此要求解最小费用最大流      容量 流量  单位流量费用        (cap,flow,cost)    v1--------------------->v2    混合网络    每个顶点有        (3,2,1)    v1--------------------->v2    v1<---------------------v2        (0,-2,-1)算法过程:    (1)先找最小费用路,在该路径上增流，称为最小费用路算法。    (2)先找最大流,然后找负费用圈，消减费用，减少到最小费用，称为消圈法    最小费用路算法，是在残余网络上寻找从源点到汇点的最小费用路，即从源点到汇点的    以单位费用为权的最短路，然后沿着最小费用路增流，知道找不到最小费用路为止。*/#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int INF=1000000;//正无穷const int NODESIZE=100;//结点最大个数const int EDGESIZE=10000;//最大边数int top;//当前边下标int maxflow;//最大流bool vis[NODESIZE];//访问标记数组int c[NODESIZE];//入队次数int dist[NODESIZE];//dist[i]表示源点到点i最短距离:距离即这条路单位cost和int pre[NODESIZE];//前驱数组struct Vertex{
   //邻接表头节点    int first;//与之连接的边的序号}V[NODESIZE];struct Edge{
   //边表示    int v,next;//v弧头 next指向下一条邻接边    int cap,flow,cost;}E[EDGESIZE];void init();//初始化void add(int u,int v,int c,int cost);//更新混合网络void add_edge(int u,int v,int c,int cost);//更新混合网络边void printgraph(int n);//输出网络邻接表void printflow(int n);//输出实流边int MCMF(int s,int t,int n);//最小花费最大流bool SPFA(int s,int t,int n);//求最小费用路int main(void){
       int nodeSize,edgeSize;    int unode,vnode,weight,cost;    cout<<"请输入 结点个数 和 边数: \n";    cin>>nodeSize>>edgeSize;    //初始化    init();    cout<<"请输入两个结点u,v,边u---v的容量weight,单位容量费用cost:\n";    for(int i=1;i<=edgeSize;i++){
           cin>>unode>>vnode>>weight>>cost;        add(unode,vnode,weight,cost);    }    //输出网络邻接表    printgraph(nodeSize);    cout<<"网络的最小费用:"<
       
        <
        
         v //构建邻接表：头插法 顺序存储法 E[top].v=v; E[top].cap=c; E[top].flow=0; E[top].cost=cost; E[top].next=V[u].first;//.next记录链的结点，下一个边的下标 V[u].first=top++;//顺序存储拉链}//输出网络邻接表void printgraph(int n){ cout<<"\n网络邻接表\n"; for(int i=1;i<=n;i++){ cout<<"v"<
         <<" ["<
          
           0){ cout<<"v"<
           <<"--"<<"v"<
            
             <<" "<
             
              <<" "<
              
               <<"\n"; } } }}//最小花费最大流int MCMF(int s,int t,int n){ int d;//可增量 int i,mincost; mincost=0;//maxflow为网络当前最大流量，mincost为网络当前最小费用 while(SPFA(s,t,n)){ //有从s到t的最小费用路 d=INF;//初始化增流量 cout<<"增广路径: "<
               
                v u<----v u---->v u<---v,通俗些就是u-->v就v<---u v<--u u-->v d=min(d,E[i].cap-E[i].flow);//迭代找最小可增量 cout<<"--"<