给你一个mn的格子的棋盘,每个格子里面有一个非负数。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取数所在的2个格子不能相邻,并且取出的数的和最大。
Input
包括多个测试实例,每个测试实例包括2整数m,n和mn个非负数(m<=50,n<=50)
Output
对于每个测试实例,输出可能取得的最大的和
Sample Input
3 3
75 15 21
75 15 28
34 70 5
Sample Output
188
第一次做根本没想到是网络流,这次搜网络流的题目找到了这道题,从一个矩阵中找出若干个不相邻的数使得权值和最大
咋一看是dp啥的,但其实这是一个二分图的问题,可以观察看出x坐标和y坐标之和的奇偶性可以来判断是否相邻,所以就可以将矩阵中的数分为两半,就是一个二分图了,所以要求的就是这个二分图的最大点权独立集,然后由
最大流=最小割=最小点权覆盖=点权和-最大点权独立集
直接模板求出最大流即可
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
//#define _clr(x,a) memset(x,a,sizeof(x))
using namespace std;
const int N=1e5+10;
const int M=1e5+50;
const int INF=0x3f3f3f3f;
int n,m;
int x;
int head[N];
int tot;
int dep[N];
int s,t;
int cur[N];
struct Edge{
int u,v,w,next;
}edge[M];
void init(){
tot=0;
memset(head,-1,sizeof(head));
}
void addEdge(int u,int v,int w){
edge[tot]=Edge{u,v,w,head[u]};
head[u]=tot++;
edge[tot]=Edge{v,u,0,head[v]};
head[v]=tot++;
}
bool bfs(){
queue<int> q;
memset(dep,0,sizeof(dep));
dep[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
int w=edge[i].w;
if(w>0 && dep[v]==0){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t]!=0;
}
int dfs(int u,int flow){
if(u==t){
return flow;
}
for(int &i=cur[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
int w=edge[i].w;
if(dep[v]==dep[u]+1 && w!=0){
int dis=dfs(v,min(w,flow));
if(dis>0){
edge[i].w-=dis;
edge[i^1].w+=dis;
return dis;
}
}
}
return 0;
}
int dinic(){
int ans=0;
while(bfs()){
for(int i=0;i<=t;i++){
cur[i]=head[i];
}
while(int d=dfs(s,INF)){
ans+=d;
}
}
return ans;
}
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int main(void){
while(~scanf("%d%d",&n,&m)){
init();
s=n*m;
t=n*m+1;
int sum=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&x);
if((i+j)%2){
addEdge(s,i*m+j,x);
if(i>0){
addEdge(i*m+j,(i-1)*m+j,INF);
}
if(i<n-1){
addEdge(i*m+j,(i+1)*m+j,INF);
}
if(j>0){
addEdge(i*m+j,i*m+j-1,INF);
}
if(j<m-1){
addEdge(i*m+j,i*m+j+1,INF);
}
}
else{
addEdge(i*m+j,t,x);
}
sum+=x;
}
}
int ans=dinic();
printf("%d\n",sum-ans);
}
return 0;
}