题目背景
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
思路：
方格分为两部分，可以看成一个二分图，假设所有点都选，那么只要找出一部分不选的，使得这部分的值最小就可以。然后转换到了二分图的最小割上。起点和终点与点之间的连边的流量为点权，不选这个点，只要将这条边割掉就好。这个二分图的点的连边，表示两个点不能共存，所以目标是让加入起点和终点的图没有从起点到终点的路径，因此转换到了最小割。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#include<bitset>
#include<time.h>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
struct node{int v,nxt,w;
}e[1000005<<1];
int tot,head[10050];
int st,ed;
int dis[10050],q[10050];
void add(int u,int v,int w){e[tot].v=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++;e[tot].v=u; e[tot].w=0; e[tot].nxt=head[v]; head[v]=tot++;
}
int bfs(int st,int ed){for(int i=st;i<=ed;i++) dis[i]=-1;int front=0,tail=0;q[tail++]=st;dis[st]=0;while(front<tail){int cur=q[front++];if(cur==ed) return 1;for(int i=head[cur];i!=-1;i=e[i].nxt){if(e[i].w&&dis[e[i].v]<0){q[tail++]=e[i].v;dis[e[i].v]=dis[cur]+1;}}}if(dis[ed]==-1) return 0;return 1;
}
ll dfs(int cur,int lim){if(lim==0||cur==ed) return lim;ll w,flow=0;for(int i=head[cur];i!=-1;i=e[i].nxt){if(e[i].w&&dis[e[i].v]==dis[cur]+1){w=dfs(e[i].v,min(lim,e[i].w));e[i].w-=w;e[i^1].w+=w;flow+=w;lim-=w;if(lim==0) break;}}if(!flow) dis[cur]=-1;return flow;
}
ll dinic(){ll ans=0;while(bfs(st,ed)) ans+=dfs(st,0x7fffffff);return ans;
}
int n,m,x,nx[4][2]={0,1,0,-1,1,0,-1,0};
ll sum=0;
int id(int x,int y){return (x-1)*m+y;
}
int main(){cin>>n>>m;ed=m*n+1;for(int i=0;i<=ed+10;i++) head[i]=-1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&x);sum+=x; if((i+j)%2==1) add(st,id(i,j),x);else add(id(i,j),ed,x);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if((i+j)%2==1){for(int k=0;k<4;k++){int tx=i+nx[k][0];int ty=j+nx[k][1];if(tx<=0||ty<=0||tx>n||ty>m)continue;add(id(i,j),id(tx,ty),inf);}}}}sum-=dinic();printf("%lld\n",sum); return 0;
}