[文章目录]
Description
在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。n<=30
为毛我没有想到黑白染色啊。。。
发现黑白染色之后就只是两个集合了。那么转化为最小割，s向其中一个集合连边，流量为数值，另一个集合向t连边，流量为数值，相邻两点连边为inf，那么两个点至少有一个被割掉了。满足题意。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,s,t;
int head[1100],to[11000],nxt[11000],f[11000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[1100];
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=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) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d",&n); ll sum=0; int x; s=n*n+1; t=s+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&x);
if((i+j)&1) add(s,(i-1)*n+j,x);
else add((i-1)*n+j,t,x);
sum+=x;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) if((i+j)&1)
{
if(i!=1) add((i-1)*n+j,(i-2)*n+j,inf);
if(i!=n) add((i-1)*n+j,i*n+j,inf);
if(j!=1) add((i-1)*n+j,(i-1)*n+j-1,inf);
if(j!=n) add((i-1)*n+j,(i-1)*n+j+1,inf);
}
while(bfs()) sum-=dinic(s,inf);
printf("%lld",sum);
return 0;
}