25-伪代码详解

7.4.4　伪代码详解

（1）定义结构体

结构体的定义和7.3.6节中改进算法ISAP中的结构体相同，边仅多了一个cost域。first指向第一个邻接边，next是下一条邻接边。该结构体用于创建邻接表。

struct Vertex    //邻接表头结点
{
    int first; 
}V[N]; 
struct Edge      //边结点
{
    int v, next; //v为弧头，next指向下一条邻接边
    int cap, flow,cost; 
}E[M];

（2）创建残余网络边

正向边的容量为cap，流量为0，费用为cost，反向边容量为0，流量为0，费用为−cost。

void add_edge(int u, int v, int c,int cost) //创建边
{
     E[top].v = v; 
     E[top].cap = c; 
     E[top].flow = 0; 
     E[top].cost = cost; 
     E[top].next = V[u].first; 
     V[u].first = top++;
}
void add(int u,int v, int c,int cost)       //添加两条边，正向边和反向边
{
     add_edge(u,v,c,cost); 
     add_edge(v,u,0,-cost); 
}

（3）求最小费用路

先初始化每个结点的距离为无穷大，然后令源点的距离dist[v₁]=0。在混合网络中，从源点出发，沿可行边（E[i].cap>E[i].flow）广度搜索每个邻接点，如果当前距离dist[v]>dist[u]+ E[i].cost，则更新为最短距离dist[v]=dist[u]+E[i].cost，并记录前驱。

bool SPFA(int s, int t, int n)      //求最小费用路的SPFA
{
     int i, u, v; 
     queue <int> qu;                //队列
     memset(vis,false,sizeof(vis)); //访问标记初始化
     memset(c,0,sizeof(c));         //入队次数初始化
     memset(pre,-1,sizeof(pre));    //前驱初始化
     for(i=1;i<=n;i++)
     {
          dist[i]=INF;              //距离初始化
     }
     vis[s]=true;                   //结点入队vis要做标记
     c[s]++;                        //要统计结点的入队次数
     dist[s]=0; 
     qu.push(s); 
     while(!qu.empty())
     {
          u=qu.front();
          qu.pop();
          vis[u]=false; 
          //队头元素出队，并且消除标记
          for(i=V[u].first; i!=-1; i=E[i].next)//遍历结点u的邻接表
          {
               v=E[i].v; 
               if(E[i].cap>E[i].flow && dist[v]>dist[u]+E[i].cost)//松弛操作
               {
                     dist[v]=dist[u]+E[i].cost; 
                     pre[v]=i;      //记录前驱
                     if(!vis[v])    //结点v不在队内
                     {
                            c[v]++; 
                            qu.push(v);        //入队
                            vis[v]=true;       //标记
                            if(c[v]>n)         //超过入队上限，说明有负环
                                  return false; 
                     }
               }
          }
     }
     cout<<"最短路数组"<<endl; 
     cout<<"dist[ ]="; 
     for(int i=1;i<=n;i++)
         cout<<"  "<<dist[i]; 
     cout<<endl; 
     if(dist[t]==INF) 
          return false;     //如果距离为INF，说明无法到达，返回false
     return true; 
}

（4）沿着最小费用路增流

从汇点逆向到源点，找最小可增流量d=min(d, E[i].cap−E[i].flow)。沿着增广路径正向边增流d，反向边减流d，产生的费用为mincost+=dist[t]*d。

int MCMF(int s,int t,int n) //minCostMaxFlow
{
     int d;                 //可增流量
     int i,mincost;         //maxflow 当前最大流量，mincost当前最小费用
     mincost=0; 
     while(SPFA(s,t,n))     //表示找到了从s到t的最小费用路
     {
          d=INF; 
          cout<<endl; 
          cout<<"增广路径："<<t; 
          for(i=pre[t]; i!=-1; i=pre[E[i^1].v]) //从汇点逆向沿增广路找最小可增量
          {
               d=min(d, E[i].cap-E[i].flow);    //找最小可增流量
               cout<<"--"<<E[i^1].v; 
          }
          cout<<"增流："<<d<<endl; 
          cout<<endl; 
          maxflow+=d;       //更新最大流
          for(i=pre[t]; i!=-1; i=pre[E[i^1].v])   //增广路上正向边流量+d，反向边流量-d
          {
               E[i].flow+=d; 
               E[i^1].flow-=d; 
          }
          mincost+=dist[t]*d; //dist[t]为该路径上单位流量费用之和，最小费用更新
     }
     return mincost; 
}