题目背景

none!

题目描述

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

输入输出格式

输入格式：

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

输出格式：

程序运行结束时，将取数的最大总和输出

输入输出样例

3 3

1 2 3

3 2 3

2 3 1 

11

说明

m,n<=100

/*Code by 520 -- 8.25*/

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define RE register

#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)

#define debug printf("%d %s\n",__LINE__,__FUNCTION__)

using namespace std;

const int N=,inf=,dx[]={,,,-},dy[]={,-,,};

int n,m,s,t,dis[N],to[N],net[N],w[N],h[N],cnt=;

int mp[][],ans;

il int id(int x,int y){return (x-)*m+y;}

il void add(int u,int v,int c){

    to[++cnt]=v,net[cnt]=h[u],w[cnt]=c,h[u]=cnt;

    to[++cnt]=u,net[cnt]=h[v],w[cnt]=,h[v]=cnt;

}

queue<int>q;

il bool bfs(){

    memset(dis,-,sizeof(dis));

    q.push(s),dis[s]=;

    while(!q.empty()){

        RE int u=q.front();q.pop();

        for(RE int i=h[u];i;i=net[i])

            if(dis[to[i]]==-&&w[i]) dis[to[i]]=dis[u]+,q.push(to[i]);

    }

    return dis[t]!=-;

}

int dfs(int u,int op){

    if(u==t)return op;

    int flow=,used=;

    for(RE int i=h[u];i;i=net[i]){

        int v=to[i];

        if(dis[to[i]]==dis[u]+&&w[i]){

            used=dfs(to[i],min(op,w[i]));

            if(!used)continue;

            flow+=used,op-=used;

            w[i]-=used,w[i^]+=used;

            if(!op)break;

        }

    }

    if(!flow) dis[u]=-;

    return flow;

}

il void init(){

    scanf("%d%d",&n,&m),t=n*m+;

    For(i,,n) For(j,,m) {

        scanf("%d",&mp[i][j]),ans+=mp[i][j];

        (i+j)&?add(s,id(i,j),mp[i][j]):add(id(i,j),t,mp[i][j]);

    }

    For(i,,n) For(j,,m)

        if((i+j)&) {

            For(k,,){

                RE int xx=i+dx[k],yy=j+dy[k];

                if(xx>&&xx<=n&&yy>&&yy<=m) add(id(i,j),id(xx,yy),inf);

            }

        }

    while(bfs()) ans-=dfs(s,inf);

    cout<<ans;

}

int main(){

    init();

    return ;

}