69-伪代码详解

7.10.4　伪代码详解

（1）构建网络

根据输入的数据，按顺序对景点编号，即景点i对应结点i，对每个结点拆点，拆为两个结点i和i'，且从i到i'连接一条边，边的容量为1，费用为0；源点和终点拆点时，边的容量为1，费用为0；如果景点i到景点j可以直达，则从结点i'到结点j连接一条边，边的容量为1，单位流量费用为−1。

cout<<"请输入景点个数n和直达线路数m："<<endl;
     cin>>n>>m; 
     init();//初始化
     maze.clear();
     cout<<"请输入景点名str"<<endl;
     for(i=1;i<=n;i++)
     {
         cin>>str[i];
         maze[str[i]]=i;
         if(i==1||i==n)
             add(i,i+n,2,0);
         else
            add(i,i+n,1,0);
     }
     cout<<"请输入可以直达的两个景点名str1，str2"<<endl;
     for(i=1;i<=m;i++)
     {
          cin>>str1>>str2;
          int a=maze[str1],b=maze[str2];
          if(a<b)
          {
             if(a==1&&b==n)
                 add(a+n,b,2,-1);
             else
                 add(a+n,b,1,-1);
          }
          else
          {
              if(b==1&&a==n)
                  add(b+n,a,2,-1);
              else
                  add(b+n,a,1,-1); 
           }
     }

（2）求网络最小费用最大流

使用最小费用路最大流算法，详见7.5.5节中的算法program 7-4，这里不再赘述。

bool SPFA(int s, int t, int n)   //求最小费用路的SPFA
{
     int i, u, v; 
     queue <int> qu;             //队列，STL实现
     memset(vis,0,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;
}
int MCMF(int s,int t,int n)                    //minCostMaxFlow
{
     int d;                                    //可增流量
     maxflow=mincost=0;//maxflow 当前最大流量，mincost当前最小费用
     while(SPFA(s,t,n))//表示找到了从s到t的最短路
     {
          d=INF;
          cout<<endl;
          cout<<"增广路径："<<t;
          for(int 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;
          for(int i=pre[t]; i!=-1; i=pre[E[i^1].v])//修改混合网络，增加增广路上相应弧的容量，并减少其反向边容量
          {
               E[i].flow+=d;
               E[i^1].flow-=d;
          }
          maxflow+=d;          //更新最大流
          mincost+=dist[t]*d;  //dist[t]为该路径上单位流量费用之和，最小费用更新
    }
    return maxflow; 
}

（3）输出最优的旅游路线

从源点出发，沿着flow>0且cost0的方向深度优先遍历，到达终点后，再沿着flow<0且cost0的方向深度优先遍历，返回到源点。

输出：首先是出发景点名，然后按遍历顺序列出其他景点名，最后回到出发景点。如果问题无解，则输出“No Solution!”。

void print(int s,int t) 
{
     int v; 
     vis[s]=1; 
     for(int i=V[s].first;~i;i=E[i].next)
       if(!vis[v=E[i].v]&&((E[i].flow>0&&E[i].cost<=0)||(E[i].flow<0&&E[i]. cost>=0)))
       {
           print(v,t);
           if(v<=t)
              cout<<str[v]<<endl;
       }
}