P2774 方格取数问题

题目背景

none!

题目描述

在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

输入输出格式

输入格式：
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。

输出格式：
程序运行结束时，将取数的最大总和输出

思路

我们用黑白染色把他分成一个二分图，假设他们最开始联通，那么图中剩余的便是最小割，取的数为总点权减去最小割
最小割=最大流（最小割定理）
建模：
S(->)黑点，容量为点权
白点(->T)，容量为点权

代码

#include<bits/stdc++.h>
#define inf 1<<30
using namespace std;
const int maxn=10000+100,maxm=200000+100;
int head[maxn],vis[maxn];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int size=1;
int n,m;
int s,t;
int sum;
struct edge
{
	int to,next,cap; 
}e[maxm];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f; 
}
void addedge(int u,int v,int val)
{
	e[++size].to=v;e[size].cap=val;e[size].next=head[u];head[u]=size;
	e[++size].to=u;e[size].cap=0;e[size].next=head[v];head[v]=size;
} 
int f(int i,int j)
{
	return (i-1)*n+j;
}
int dfs(int u,int f)
{
	if(u==t)
	return f;
	vis[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{	
		int to=e[i].to;
		if(!vis[to]&&e[i].cap>0)
		{
			int d=dfs(to,min(f,e[i].cap));
			if(d>0)
			{
				e[i].cap-=d;
				e[i^1].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
int maxflow()
{
	int flow=0;
	while(1)
	{
		memset(vis,0,sizeof(vis));
		int f=dfs(s,inf);
		if(f==0)return flow;
		flow+=f;
	}
}
int main()
{
    m=read(),n=read();
    s=0,t=m*n+2;
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
      {
    	int u=f(i,j);
    	int w=read();
    	sum+=w;
    	if((i+j)&1)addedge(s,u,w);//i+j为奇数偶数则为黑白
    	else addedge(u,t,w);
      }
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
      {
      	int u=f(i,j);
      	if((i+j)&1)
      	{
      	  for(int k=0;k<4;k++)
      	  {
      		int nx=i+dx[k],ny=j+dy[k];
      		if(nx<=0||nx>m||ny<=0||ny>n)continue;
      		int v=f(nx,ny);
      		addedge(u,v,inf);
		  }
	    }
	  }
	printf("%d",sum-maxflow());
	return 0; 
}