62-伪代码详解

7.9.4　伪代码详解

（1）构建网络

根据输入的数据，按行编号，根据编号黑白染色。添加源点和汇点，从源点s向黑色方格连一条边，容量为该黑色方格的权值，从白色方格向汇点t连一条边，容量为该白色方格的权值，对于每一对相邻的黑白方格，从黑方格向白方格连一条边，容量为∞，创建混合网络。

//创建混合网络
for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        if((i+j)%2==0)                  //染黑色,当前物品位置(i,j) 
        {
             add(0,(i-1)*n+j,map[i][j]);//从源点到当前物品结点有一条有向边，容量为该物品价值
             flag[(i-1)*n+j]=1;         //标记染黑色物品
             //当前物品结点到四个相邻物品结点发出一条有向边，容量为无穷大
             for(int k=0;k<4;k++)
             {
                  int x=i+dir[k][0]; 
                  int y=j+dir[k][1]; 
                  if(x<=m&&x>0 && y<=n&&x>0)//边界限制
                      add((i-1)*n+j,(x-1)*n+y,INF); 
             }
        }
        else                            //染白色,当前物品位置(i,j) 
           add((i-1)*n+j,total+1,map[i][j]);//从当前物品结点到汇点有一条有向边，容量为该物品价值
     }

（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集合中的黑色方格和T集合中的白色方格。从源点出发，在最大流对应的混合网络上，沿着cap>flow的边深度优先遍历，遍历到的结点就是S集合，没遍历到的结点就是T集合。输出S集合中的黑色方格，输出T集合的白色方格。

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(!dfsflag[u]) 
             {
                   dfsflag[u]=true; 
                   DFS(u); 
             }
         }
}
void print(int m,int n)//输出最佳方案
{
    cout<<"----------最佳方案如下：----------"<<endl; 
    cout<<"选中的物品编号："<<endl; 
    DFS(0); 
    for(int i=1;i<=m*n;i++)
         if((flag[i]&&dfsflag[i])||(!flag[i]&&!dfsflag[i])) 
                cout<<i<<"  ";
}