P2774 方格取数问题
题目背景
none!
题目描述
在一个有 \(m*n\) 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入输出格式
输入格式：
第 \(1\) 行有 \(2\) 个正整数 \(m\) 和 \(n\)，分别表示棋盘的行数和列数。接下来的 \(m\) 行，每行有 \(n\) 个正整数，表示棋盘方格中的数。
输出格式：
程序运行结束时，将取数的最大总和输出
说明
\(n,m\le 100\)
积累一下思维方式
棋盘不妨先进行黑白染色，然后可以得到一个二分图。
考虑我们需要把点集划分成两份，两份之间没有边连接，可以联想到最小割是做这个的。
最小割割的是边，想办法把点权搞到边上，因为我们本来就是二分图，所以两边源汇直接连点权的容量，图两边连inf，表示割不掉。其余边割掉代表割的是点，然后就把两个图搞不连通了。
Code:
#include <cstdio>
#include <cstring>
const int N=1e4+10;
const int inf=0x3f3f3f3f;
int min(int x,int y){return x<y?x:y;}
int head[N],to[N<<4],Next[N<<4],edge[N<<4],cnt=1;
void add(int u,int v,int w)
{
to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;
to[++cnt]=u,edge[cnt]=0,Next[cnt]=head[v],head[v]=cnt;
}
int q[N],l,r,dep[N],n,m,s,t,sum;
bool bfs()
{
memset(dep,0,sizeof dep);
dep[q[l=r=1]=s]=1;
while(l<=r)
{
int now=q[l++];
for(int v,i=head[now];i;i=Next[i])
if(!dep[v=to[i]]&&edge[i])
{
dep[v]=dep[now]+1;
if((q[++r]=v)==t) return true;
}
}
return false;
}
int dfs(int now,int flow)
{
if(now==t) return flow;
int res=flow,bee;
for(int v,i=head[now];i&&res;i=Next[i])
if(dep[v=to[i]]==dep[now]+1&&edge[i])
{
bee=dfs(v,min(res,edge[i]));
if(!bee) dep[v]=0;
edge[i]-=bee,edge[i^1]+=bee;
res-=bee;
}
return flow-res;
}
const int dx[5]={0,-1,0,1,0};
const int dy[5]={0,0,1,0,-1};
int main()
{
scanf("%d%d",&n,&m);
s=n*m+1,t=s+1;
for(int x,i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&x);
sum+=x;
int id=(i-1)*m+j;
if(i+j&1)
{
add(s,id,x);
for(int k=1;k<=4;k++)
{
int di=i+dx[k],dj=j+dy[k];
if(di&&dj&&di<=n&&dj<=m)
add(id,(di-1)*m+dj,inf);
}
}
else add(id,t,x);
}
int flow,maxflow=0;
while(bfs())
if(flow=dfs(s,inf)) maxflow+=flow;
printf("%d\n",sum-maxflow);
return 0;
}
2019.1.16