55-伪代码详解

7.8.4　伪代码详解

（1）构建混合网络

根据输入的数据，添加源点和汇点，从源点s到每个实验项目E_i有一条有向边，容量是项目产生的效益p_i，从每个实验仪器I_j到汇点t有一条有向边，容量是仪器费用c_j，每个实验项目到该实验项目用到的仪器有一条有向边容量是∞，创建混合网络。混合网络边的结构体见7.3.7节中改进的最短增广路算法ISAP。

    cout<<"请输入实验数m和仪器数n："<<endl; 
    cin>>m>>n; 
    init();
    total=m+n; 
    cout<<"请依次输入实验产生的效益和该实验需要的仪器编号（为0结束）："<<endl; 
    for(int i=1;i<=m;i++)
    {
         cin>>cost; 
         sum+=cost; 
         add(0, i, cost);//源点到实验项目的边，容量为该项目效益
         while(cin>>num,num) //num为该项目需要的仪器编号
              add(i, m+num, INF);//实验项目到需要仪器的边，容量为无穷大
    }
    cout<<"请依次输入所有仪器的费用："<<endl; 
    for(int j=m+1;j<=total;j++)
    {
         cin>>cost; 
         add(j, total+1, cost);//实验仪器到汇点的边，容量为实验仪器费用
    }

（2）求网络最大流

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

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

（3）输出实验方案的净收益

cout<<"最大净收益："<<sum-Isap(0,total+1,total+2)<<endl; //所有实验项目收益−最大流值

（4）输出选中的实验项目和仪器编号

在最大流对应的混合网络中，从源点s开始，沿着cap>flow的边深度优先遍历，遍历到的结点对应的实验项目和仪器就是选中的实验方案。

void DFS(int s)                         //深度搜索最大获益方案
{
    for(int i=V[s].first;~i;i=E[i].next)//读当前结点的邻接表
         if(E[i].cap>E[i].flow) 
         {
              int u=E[i].v; 
              if(!flag[u]) 
              {
                   flag[u]=true; 
                   DFS(u); 
              }
         }
}
void print(int m,int n)//输出最佳方案
{
    cout<<"----------最大获益方案如下：----------"<<endl; 
    DFS(0); 
    cout<<"选中的实验编号："<<endl; 
    for(int i=1;i<=m;i++)
         if(flag[i]) 
              cout<<i<<"  ";
    cout<<endl; 
    cout<<"选中的仪器编号："<<endl; 
    for(int i=m+1;i<=m+n;i++)
        if(flag[i]) 
              cout<<i-m<<"  ";
}