48-伪代码详解

7.7.4　伪代码详解

（1）构建混合网络

根据输入的数据，建立二分图，每个题型为X集合中的结点，每个试题为Y集合中的结点，增设源点s和汇点t。从源点s向每个题型x_i结点连接一条有向边，容量为该题型选出的数量c_i。从每个y_j结点向汇点t连接一条有向边，容量为1，以保证每道题只能选中一次。Y集合中的题y_j属于哪些题型，则这些题型x_i与y_j之间有一条有向边，容量为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<<"请依次输入每个试题所属的题型（0结束）："<<endl; 
   for(int j=m+1;j<=total;j++)
   {
        while(cin>>num,num)  //num为试题j属于的题型号，为0时结束
             add(num, j, 1); //题型号num到试题j的边，容量为1
        add(j, total+1,1);   //试题j到汇点的边，容量为1
   }

（2）求网络最大流

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

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

（3）输出抽取方案

如果最大流值等于源点s与X（题型）集合所有结点边容量之和，则说明试题抽取成功，否则无解。对于每个题型，从X集合对应题型结点出发，所有流量为1的边指向的Y集合的结点就是该题型选中的试题号。即x_i结点在Y集合的所有流量为1的邻接结点就是该题型选中的试题号。在程序中，试题存储编号=试题实际编号+题型数m，输出时需要输出试题实际编号，即试题存储编号−m。

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; 
    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; 
    }
}