codevs 1907 方格取数 3

Description

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

Input

第1 行有2 个正整数m和n，分别表示棋盘的行数和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。

Output

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

Sample Input

3 3
1 2 3
3 2 3
2 3 1

Sample Output

HINT

n,m<=30

　　嗯......这道题大概算是自己想出来的第一道网络流的题吧？

　　虽然想了很久，WA了很多发，但终于A掉了......

　　网络流的题真是难想(但这一题还是比较简单的)，如果不是我已经知道这道题要用网络流做，还不知道要想到什么时候去了......

　　好了，不扯多了，进正题：

　　首先，我们发现直接建模的话非常不好搞，体重的条件不好表示......

　　于是，我们就想，是否可以把我们选完数之后剩下的数给表示出来呢？我们发现这个不难做到。只需将棋盘黑白二染色，把黑点、白点各看成一块，相邻的格子间有边相连，不难发现将黑白两块分开的割的方案就是不选的点的合法方案（脑补一下应该可以搞出来）。所以最小割即是合法方案中选出的点和最大的方案。于是我们可以从源点向所有黑(白)点连一条容量为这个格子里的数的边，从黑(白)点向相邻的点连一条容量为INF的边，再从白(黑)点向汇点连一条容量为当前格子里的数的边，跑一边最大流即可得出不选的点的最小和，用所有数字之和减去它就是答案。

　　update:其实这就是最大独立集等于总点数减去最大匹配数

　　下面贴代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define maxm 100010

 #define INF (1<<25)

 #define r(j) (j^1)

 using namespace std;

 typedef long long llg;

 int head[*],next[maxm],to[maxm],c[maxm],tt=;

 int a[][],zx[]={,,,-},zy[]={,-,,};

 int d[maxm],l,r,dep[maxm],ans,tut,s,t,n,m;

 int getint(){

     int w=;bool q=;

     char c=getchar();

     while((c>''||c<'')&&c!='-') c=getchar();

     if(c=='-') q=,c=getchar();

     while(c>=''&&c<='') w=w*+c-'',c=getchar();

     return q?-w:w;

 }

 void link(int x,int y,int z){

     to[++tt]=y;next[tt]=head[x];head[x]=tt;

     to[++tt]=x;next[tt]=head[y];head[y]=tt;

     c[tt^]=z;

 }

 bool bfs(){

     for(int i=;i<=t;i++) dep[i]=;

     l=r=;d[r++]=s;dep[s]=;int u;

     while(l!=r){

         u=d[l++];

         for(int i=head[u];i;i=next[i])

             if(!dep[to[i]] && c[i]>){

                 dep[to[i]]=dep[u]+;

                 d[r++]=to[i];

             }

     }

     return dep[t]>;

 }

 int dfs(int u,int low){

     int res=,v;

     if(u==t) return low;

     if(!low) return ;

     for(int i=head[u];i;i=next[i])

         if(c[i]> && dep[to[i]]==dep[u]+){

             v=dfs(to[i],min(low-res,c[i]));

             c[i]-=v;c[r(i)]+=v;res+=v;

         }

     return res;

 }

 int main(){

     freopen("a.in","r",stdin);

     freopen("a.out","w",stdout);

     n=getint();m=getint();s=n*m+;t=s+;

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

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

             a[i][j]=getint();

     for(int i=,now();i<=n;i++)

         for(int j=;j<=m;j++){

             now++;

             if(!((i+j)&)){

                 link(s,now,a[i][j]);

                 for(int k=,x,y,n1;k<;k++){

                     x=i+zx[k];y=j+zy[k];

                     if(x> && x<=n && y> && y<=m){

                         n1=(x-)*m+y;

                         link(now,n1,INF);

                     }

                 }

             }

             else link(now,t,a[i][j]);

             tut+=a[i][j];

         }

     while(bfs())

         while(int tot=dfs(s,INF)) ans+=tot;

     printf("%d\n",tut-ans);

     return ;

 }

秒客网