【题目名称】：方格取数问题

Description

【问题描述】：

　　在一个有 m*n 个方格的棋盘中（1<=m,n<=30），每个方格中有一个正整数。现要从方格中取数，使任意2个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。

【编程任务】：

　　对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

Input

　　由文件input.txt提供输入数据。文件第1 行有2 个正整数 m和 n，分别表示棋盘的行数和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。

Output

　　程序运行结束时，将取数的最大总和输出到文件output.txt中。

Sample Input

　　3 3

　　1 2 3

　　3 2 3

　　2 3 1

Sample Output

　　11

【题目分析】：

【问题分析】

二分图点权最大独立集，转化为最小割模型，从而用最大流解决。

【建模方法】

首先把棋盘黑白染色，使相邻格子颜色不同，所有黑色格子看做二分图X集合中顶点，白色格子看做Y集合顶点，建立附加源S汇T。

1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。

2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。

3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。

求出网络最大流，要求的结果就是所有格子中数值之和减去最大流量。

【建模分析】

这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。

对于一个网络，除去冗余点（不存在一条ST路径经过的点），每个顶点都在一个从S到T的路径上。割的性质就是不存在从S到T的路径，简单割可以认为割边关联的非ST节点为割点，而在二分图网络流模型中每个点必关联到一个割点（否则一定还有增广路，当前割不成立），所以一个割集对应了一个覆盖集（支配集）。最小点权覆盖集就是最小简单割，求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大，此时的最小割就是最小简单割了。

有关二分图最大点权独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。

【C++源码】：

#include<iostream>

using namespace std;

const int maxn=1024;

const int oo=0x7FFFFFFF/2-5;

const int dx[]={-1,0,1,0},

          dy[]={0,-1,0,1};

struct NODE{

       int st,ed,f;

       NODE *op,*next;

       NODE(){op=next=NULL;}

       }*g[maxn],*now[maxn],*pre[maxn];

typedef int Arr1[maxn];

int m,n;

int ST,ED;

int sum=0;

int a[55][55]={0};

Arr1 dis={0};

Arr1 back={0};

Arr1 sumd={0};

bool flag;

bool cor[55][55]={0};

void add(int st,int ed,int f)

{

     NODE *x,*y;

     x=new NODE;

     y=new NODE;

     x->op=y;

     y->op=x;

     x->st=st,x->ed=ed,x->f=f,x->next=g[st],g[st]=x;

     y->st=ed,y->ed=st,y->f=0,y->next=g[ed],g[ed]=y;

}

void Color(){

     int i,j,k;

     for( i=1 ;i<=m ;i+=2 ) cor[1][i]=1;

     for( i=2 ;i<=n ;i++ )

     {

          for( j=1 ;j<=m ;j++ ) cor[i][j]=!cor[i-1][j];

     }

}

void init(){

     int st,ed,v;

     int i,j,k,t;

     scanf("%d%d",&n,&m);

     Color();

     ST=n*m+1;

     ED=n*m+2;

     for( i=1 ;i<=n*m+10 ;i++ ) g[i]=NULL;

     for( i=1 ;i<=n ;i++ )

          for( j=1 ;j<=m ;j++ )

          {

               scanf("%d",&a[i][j]);//cin>>a[i][j];

               sum+=a[i][j];

          }

     for( i=1 ;i<=n ;i++ )

          for( j=1 ;j<=m ;j++ )

          {

               int num=m*(i-1)+j;

               if( cor[i][j] )

                   add(ST,num,a[i][j]);

               else

                   add(num,ED,a[i][j]);

               if( cor[i][j] )

               for( k=0 ;k<4 ;k++ )

               {

                    int nx,ny;

                    nx=i+dx[k];

                    ny=j+dy[k];

                    if( nx<1 || nx>n || ny<1 || ny>m ) continue;

                    int num2=m*(nx-1)+ny;

                    if( cor[i][j]!=cor[nx][ny] )

                    add(num,num2,oo);

               }

          }

     n=n*m+2;

     for( int i=1 ;i<=n ;i++ ) now[i]=g[i];

}

void SAP(){

     int i,j,k;

     int ans=0;

     int flow=0x7FFFFFFF;

     for( sumd[0]=n,i=ST ;dis[ST]<n ; )

     {

          flag=false;

          back[i]=flow;

          for( NODE *t=now[i] ;t!=NULL ;t=t->next )

          {

               j=t->ed;

               if( t->f<=0 || dis[i]!=dis[j]+1 ) continue;

               flag=true;

               now[i]=t;

               pre[j]=t;

               flow<?=t->f;

               i=j;

               if( i==ED )

               {

                   ans+=flow;

                   while( i!=ST )

                   {

                          pre[i]->f-=flow;

                          pre[i]->op->f+=flow;

                          i=pre[i]->st;

                   }

                   flow=0x7FFFFFFF;

               }

               break;

          }

          if( flag ) continue;

          int Min=n-1;

          for( NODE *t=g[i] ;t!=NULL ;t=t->next )

               if( t->f>0 && dis[t->ed]<Min )

               {

                   now[i]=t;

                   Min=dis[t->ed];

               }

          if( !(--sumd[dis[i]]) ) break;

          sumd[dis[i]=Min+1]++;

          if( i!=ST )

          i=pre[i]->st,flow=back[i];

     }

      cout<<sum-ans<<endl;

}

int main()

{

    init();

    SAP();

    return 0;

}