题目传送门(BZOJ)
>原文链接<

题解 :

​ 本题是网络流二十四题中的问题,考虑用网络流解决。

若要求选点 x ,则 x 周围的四个点都不能选,我们可以依据这个性质,把方格按 (i+j)\%2 黑白染色

对于黑色格子,我们从原点向它连一条流量为其权值的边,并且从它向周围四个格子连边,流量为 INF

对于白色格子,我们从它向汇点连一条流量为其权值的边。

之所以这样连边的原因是,我们要求一个方案不能有从 S \to x \to y \to T 的流,那么相当于割掉这些边。

为了让我们获得的权值尽可能的多,我们必须要求一个最小的割,根据 最小割 = 最大流 这个已经证明过的定理,我们可以对建出来的图求一个最大流,这样,答案就是 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}a[i][j] – MaxFlow

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 5000;const int inf = 0x3f3f3f3f;#define P(i,j) ((i-1)*m+j)int head[N],to[N<<1],val[N<<1],nxt[N<<1];int cnt = 1;int dep[N<<1], sum;int n, m, s, t;void add_edge(int a, int b, int c) { to[++cnt] = b; nxt[cnt] = head[a]; head[a] = cnt; val[cnt] = c; to[++cnt] = a; nxt[cnt] = head[b]; head[b] = cnt; val[cnt] = 0;}queue<int>q;bool bfs() { memset(dep, 0, sizeof dep); while(!q.empty()) q.pop(); q.push(s); dep[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; i; i = nxt[i]) if(!dep[to[i]]&&val[i]) { dep[to[i]] = dep[u]+1; if(to[i] == t) return 1; q.push(to[i]); } } return 0;}int dfs(int p,int mf) { int nf=0; if(p==t)return mf; for(int i=head[p];i;i=nxt[i]) { if(dep[to[i]]==dep[p]+1&&val[i]) { int tmp=dfs(to[i],min(mf-nf,val[i])); if(!tmp)dep[to[i]]=0; nf+=tmp; val[i]-=tmp; val[i^1]+=tmp; if(nf==mf)break; } } return nf;}void dinic() { int ans=0; while(bfs()) ans+=dfs(s,inf); printf("%d\n",sum-ans);}signed main() { scanf("%d",&n); m = n; s = n*m+1,t = n*m+2; for(int i = 1; i <= n; i ++ ) for(int j = 1, x; j <= m; j ++ ) { scanf("%d",&x); sum += x; if((i+j)&1) { add_edge(s, P(i, j), x); if(i>1) add_edge(P(i, j), P(i-1, j), inf); if(i<n) add_edge(P(i, j), P(i+1, j), inf); if(j>1) add_edge(P(i, j), P(i, j-1), inf); if(j<m) add_edge(P(i, j), P(i, j+1), inf); } else add_edge(P(i, j), t, x); } dinic();}