Rockdu's Blog

Input

包括多个测试实例，每个测试实例包括2整数m,n和m*n个非负数(m<=50,n<=50)

Output

对于每个测试实例，输出可能取得的最大的和

Sample Input

3 3
75 15 21 
75 15 28 
34 70 5​

Sample Output

188​​

很有意思的图论建模，首先生成一个二分图，左边的点和右边的点不可同时取。然后从超级源点向左边的每一个点连一条流量为该处数字的边，左边的点向自己上下左右四个右边的点连一条流量为无限的边，右边的点向超级汇点连该出数字流量的边。再Dinic跑一遍最大流就可以了。

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=150;
const int inf=0x3f3f3f3f;
struct edge
{
	int v,next,flow;
}e[1000100];
int head[maxn*maxn];
int iter[maxn*maxn];
int d[maxn*maxn];
bool colblk[maxn][maxn];//是否从原点出发 
int edc;

int n,m;
int mp[maxn][maxn];

void adde(int u,int v,int f)
{
	e[edc].v=v;
	e[edc].flow=f;
	e[edc].next=head[u];
	head[u]=edc++;
}

void addn(int u,int v,int f)
{
	adde(u,v,f);adde(v,u,0);
}

int getn(int x,int y)
{
	return (x-1)*n+y;
}

void init()
{
	edc=0;
	memset(head,-1,sizeof(head));
}

bool legal(int x,int y)
{
	return !(x<1 || x>m || y<1 || y>n);
}

int bfs(int s,int t)
{
	queue<int> q;
	memset(d,-1,sizeof(d));
	memcpy(iter,head,sizeof(head));
	d[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=e[i].next)
		{
			int v=e[i].v,f=e[i].flow;
			if(d[v]==-1 && f)
			{
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	return d[t]!=-1;
}

int dfs(int u,int mn,int t)
{
	if(u==t)
		return mn;
	int ret=0;
	for(int &i=iter[u];i!=-1;i=e[i].next)
	{
		int v=e[i].v;
		int f=e[i].flow;
		if(!f || d[v]!=d[u]+1)
			continue;
		int tmp=dfs(v,min(mn-ret,f),t);
		if(!tmp)	continue;
		e[i].flow-=tmp;
		e[i^1].flow+=tmp;
		ret+=tmp;
		if(ret==tmp)	
			return ret;
	}
	return ret;
}

int dinic(int s,int t)
{
	int ans=0;
	while(bfs(s,t))	ans+=dfs(s,inf,t);
	return ans;
}

int main()
{
	while(~scanf("%d%d",&m,&n))
	{
		init();
		int sum=0;
		int s=0,t=n*m+1;
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
			{
				scanf("%d",&mp[i][j]);
				sum+=mp[i][j];
				if((i%2==1 && j%2==1)||(i%2==0 && j%2==0))
					addn(s,getn(i,j),mp[i][j]),colblk[i][j]=1;
				else
					addn(getn(i,j),t,mp[i][j]),colblk[i][j]=0;
			}
		int dx[4]={0,0,-1,1};
		int dy[4]={-1,1,0,0};
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				{
					for(int k=0;k<4;k++)
						if(legal(i+dx[k],j+dy[k]))
							if(colblk[i][j]==1)
								addn(getn(i,j),getn(i+dx[k],j+dy[k]),inf);
							else
								addn(getn(i+dx[k],j+dy[k]),getn(i,j),inf);
				}
		printf("%d\n",sum-dinic(s,t));
	}
	return 0;
}