33-伪代码详解

7.5.4　伪代码详解

（1）创建混合网络邻接表

for(int i=1;i<=m;i++)
    add(0, i, 1);       //源点到女推销员的边
for(int j=m+1;j<=total;j++)
    add(j, total+1, 1); //男推销员到汇点的边
cout<<"请输入可以配合的女推销员编号u和男推销员编号v(两个都为-1结束):"<<endl; 
while(cin>>u>>v,u+v!=-2) 
    add(u,v,1);         //添加混合网络的两条边

（2）求网络最大流

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

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

（3）输出最佳配对数和配对方案

输出最大流值就是最多的配对数。搜索女推销员结点的邻接表，流量为1的边对应的邻接点就是该女推销员的配对方案。

cout<<"最大配对数:"<<Isap(0,total+1,total+2)<<endl; 
printflow(m);        //输出配对方案
void printflow(int n)//输出配对方案
{
    cout<<"----------配对方案如下：----------"<<endl; 
    for(int i=1;i<=n;i++)
       for(int j=V[i].first;~j;j=E[j].next) 
            if(E[j].flow>0) 
            {
                cout<<i<<"--"<<E[j].v<<endl; 
                break; 
            }
}