[文章目录]
Description
在一个有 m*n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 (n,m<=30)
通过想到黑白染色发现每两个有限制的点各自构成了两个集合。然后想到连边，然后问题就转化成了要求一个有点权的二分图最大点权独立集（每条边上的两个端点都不能同时在集合内），然后我就不会了。还是看了CKH的题解才会的。
%%%CKH dalao
考虑最大点权独立集是最小点权覆盖集的补集，（就是每条边上都有点覆盖的集合），又因为是求一个尽可能让它小的东西，就转化成最小割来想。（其实蒟蒻的我也不会）然后，参见CKH的blog找建图方法吧。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k1,s,t,sum;
int dis[1000];
int head[1000],to[10000],nxt[10000],f[10000],cnt=1;
void add(int x,int y,int z)
{
to[++cnt]=y;
f[cnt]=z;
nxt[cnt]=head[x];
head[x]=cnt;
to[++cnt]=x;
f[cnt]=0;
nxt[cnt]=head[y];
head[y]=cnt;
}
queue<int>q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof(dis));
q.push(s);dis[s]=0;int x,tmp;
while(!q.empty())
{
x=q.front();tmp=dis[x];q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=tmp+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
int xx,tmp=flow;
if(x==t) return flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(xx==0) dis[to[i]]=-1;
f[i]-=xx,f[i^1]+=xx;
if(!(tmp-=xx)) break;
}
return flow-tmp;
}
int main()
{
cin>>n>>m;t=n*m+m+1,s=n*m+m+2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&k1);sum+=k1;
if((i+j)&1) add(s,i*m+j,k1);
else add(i*m+j,t,k1);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i+1<=n)
if((i+j)&1) add(i*m+j,(i+1)*m+j,inf);
else add((i+1)*m+j,i*m+j,inf);
if(j+1<=m)
if(i+j&1) add(i*m+j,i*m+j+1,inf);
else add(i*m+j+1,i*m+j,inf);
}
}
while(bfs()) sum-=dinic(s,inf);
printf("%d",sum);
return 0;
}