学步园

«问题描述：
在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任
意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
«编程任务：
对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

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

将取数的最大总和输出

3 3
1 2 3
3 2 3
2 3 1

11

n,m<=30

题解

http://wikioi.com/solution/list/1907/

先吐槽一下喵……这题数据真心好水啊……写个最暴力的状压DP都能90分有木有ヽ(≧Д≦)ノ 

再说正解……

其实和1789-最大获利是类似的方法，就是先假设所有点都能取到，然后算出想要满足条件最少需要舍弃多少的价值，使用的算法是最小割：

把所有格子分成两部分，使得相邻的格子不在同一部分内（通俗地说就是黑白染色）；

然后把源点和所有黑格分别连边，边权为相应格子的价值；

把所有白格分别和汇点连边，边权为相应格子的价值；

再把每个黑格与相邻的几个白格连边，边权为正无穷；

显然，这样建图后，每种可行的割法对应着一种舍弃方案，而总价值减去最小割就是最后的答案。

数据范围挺小的，大概用什么算法都没问题……不过SAP居然秒过太可怕了………………(〜￣▽￣)〜 

代码

http://hzwer.com/1664.html

#include<iostream>
#include<cstring>
#include<cstdio>
#define INF 0x7fffffff
using namespace std;
int n,m,cnt=1,head[1001],h[1001],ans;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int mp[31][31],mark[31][31];
struct data{int to,next,v;}e[10001];
bool jud(int x,int y){if(x<1||y<1||x>n||y>m)return 0;return 1;}
void ins(int u,int v,int w)
{cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);}
void INS(){
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           if((i+j)%2==0)
           {
              insert(0,mark[i][j],mp[i][j]);
              for(int k=0;k<4;k++)
              {
                  if(jud(i+xx[k],j+yy[k])){insert(mark[i][j],mark[i+xx[k]][j+yy[k]],INF);}
                   }
            }
           else insert(mark[i][j],n*m+1,mp[i][j]);
     }
bool bfs()
{
     int q[40002],t=0,w=1,i,now;
     memset(h,-1,sizeof(h));
     q[0]=h[0]=0;
     while(t<w)
     {
            now=q[t];t++;
            i=head[now];
            while(i)
            {
                  if(e[i].v&&h[e[i].to]<0){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}
                  i=e[i].next;
             }
     }
     if(h[n*m+1]==-1)return 0;
     return 1;
     }
int dfs(int x,int f)
{
    if(x==n*m+1)return f;
    int i=head[x];
    int w,used=0;
    while(i)
    {
            if(e[i].v&&h[e[i].to]==h[x]+1)
            {
                w=f-used;
                w=dfs(e[i].to,min(w,e[i].v));   
                e[i].v-=w;
                e[i^1].v+=w;
                used+=w;
                if(used==f)return f;                      
                }
                i=e[i].next;
            }
    if(!used)h[x]=-1;
    return used;
    }
void dinic(){while(bfs())ans-=dfs(0,INF);}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
       {
          scanf("%d",&mp[i][j]);
          ans+=mp[i][j];
          }
    int b=0,w=(n*m+1)/2; 
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
           if((i+j)%2==0){b++;mark[i][j]=b;}
               else{w++;mark[i][j]=w;}
    INS();
    dinic();
    printf("%d",ans);
    return 0;
    }