41-伪代码详解

7.6.4　伪代码详解

（1）构建混合网络

从源点s向每个x_i结点连接一条容量为该代表团人数r_i的有向边。从每个y_j结点向汇点t连接一条容量为该会议桌容量c_j的有向边。X集合中每个结点向Y集合中每个结点连接一条容量为1的有向边。创建混合网络，混合网络边的结构体见7.3.7节中改进的最短增广路算法ISAP。

    cout<<"请输入代表团数m和会议桌数n："<<endl; 
    cin>>m>>n; 
    init();
    total=m+n; 
    cout<<"请依次输入每个代表团人数："<<endl; 
    for(int i=1;i<=m;i++)
    {
         cin>>cost; 
         sum+=cost; 
         add(0, i, cost);      //源点到代表团的边，容量为该代表团人数
    }
    cout<<"请依次输入每个会议桌可安排人数："<<endl; 
    for(int j=m+1;j<=total;j++)
    {
         cin>>cost; 
         add(j, total+1, cost);//会议桌到汇点的边，容量为会议桌可安排人数
    }
    for(int i=1;i<=m;i++)
         for(int j=m+1;j<=total;j++)
             add(i, j, 1);     //代表团到会议桌的边，容量为1

（2）求网络最大流

int Isap(int s, int t,int n)//改进的最短增广路算法

详见7.3.7节的算法program 7-2-1，这里不再赘述。

（3）输出安排方案

如果流量等于源点s与X集合所有结点边容量之和，那么说明X集合每个点都有完备的多重匹配，否则无解。对于每个单位，从X集合对应点出发的所有流量为1的边指向的Y集合的结点就是该单位人员的安排情况（一个可行解）。即x_i结点的在Y集合的所有邻接结点就是代表团x_i的人员会议桌安排。

if(sum==Isap(0,total+1,total+2)) 
     {
        cout<<"会议桌安排成功！";
        cout<<endl; 
        print(m,n);     //输出安排方案
        cout<<endl; 
        printg(total+2);//输出最终网络邻接表
     }
     else
        cout<<"无法安排所有代表团！";
void print(int m,int n) //输出最佳方案
{
    cout<<"----------安排方案如下：----------"<<endl; 
    cout<<"每个代表团的安排情况："<<endl; 
    for(int i=1;i<=m;i++)                    //读每个代表团的邻接表
    {
         cout<<"第"<<i<<"个代表团安排的会议桌号：";
         for(int j=V[i].first;~j;j=E[j].next)//读第i个代表团的邻接表
              if(E[j].flow==1) 
                   cout<<E[j].v-m<<"  ";
         cout<<endl; 
    }
}