题目背景
none!
题目描述
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入输出格式
输入格式：
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
输出格式：
程序运行结束时，将取数的最大总和输出
输入输出样例
输入样例#1：
3 3 1 2 3 3 2 3 2 3 1
输出样例#1：
11
说明
none!
解题思路
一道和骑士共存问题差不多的题目，二分图黑白染色后跑最大独立集，这里每个白格向四周连边，而不是马能攻击到的地方(废话)。
源代码
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> int n,m; int a[1000][1000]={0}; int S=0; inline int id(int x,int y) { return (x-1)*m+y; } int s,t; struct Edge{ int next,to,flow; }e[1000010]; int cnt=2,head[1000]={0}; void add(int u,int v,int f) { e[cnt]={head[u],v,f}; head[u]=cnt++; e[cnt]={head[v],u,0}; head[v]=cnt++; } int dis[1000]={0}; bool bfs() { memset(dis,0,sizeof(dis)); std::queue<int> q; q.push(s); dis[s]=1; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]||!e[i].flow) continue; dis[v]=dis[u]+1; q.push(v); } } return dis[t]!=0; } int dfs(int u,int f) { if(u==t||f==0) return f; int flow_sum=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]!=dis[u]+1||!e[i].flow) continue; int temp=dfs(v,std::min(e[i].flow,f-flow_sum)); e[i].flow-=temp; e[i^1].flow+=temp; flow_sum+=temp; if(flow_sum>=f) break; } if(!flow_sum) dis[u]=-1; return flow_sum; } int dinic() { int ans=0; while(bfs()) { while(int temp=dfs(s,0x7fffffff)) ans+=temp; } return ans; } int main() { scanf("%d%d",&n,&m); s=n*m+1,t=s+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),S+=a[i][j]; int bh[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if((i+j)&1) { add(s,id(i,j),a[i][j]); for(int k=0;k<4;k++) { int x=i+bh[k][0],y=j+bh[k][1]; if(x>=1&&x<=n&&y>=1&&y<=m) add(id(i,j),id(x,y),0x7fffffff); } } else add(id(i,j),t,a[i][j]); } } printf("%d ",S-dinic()); return 0; }