题目背景
none!
题目描述
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入输出格式
输入格式：
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
输出格式：
程序运行结束时，将取数的最大总和输出
输入输出样例
输入样例#1：
3 3
1 2 3
3 2 3
2 3 1
输出样例#1：
11
说明
m,n<=100
Solution:
网络流套路题。
一个点若选，会使得其四方向邻格不能被选，若以坐标和的奇偶性为基准，则图会被分为两部分，不难发现同一部分的点是不会互相影响的，这恰好是二分图的形式。
我们从$s$向所有奇数点连点值大小的边，从偶数点向$t$连点值大小的边，然后从奇数点向受影响的偶数点连inf的边。由于要求的是点值和最大的情况，先要使选的情况合法（即使$s,t$不联通），且不选的点值和最小，那么这不就是最小割嘛！所以只要用点值和-最小割就是答案了。（好套路的黑白点啊）
代码：
/*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 ;
}