首页 > 代码库 > HDU1565_方格取数(1)

HDU1565_方格取数(1)

2024-07-10 22:10:04   216人阅读

给一个数字方阵，你要从中间取出一些数字，保证相邻的两个数字不同时被取出来，求取出来的最大的和是多少？

建立图模型，对于行列的和为奇数的格子，建立一条从原点到达这个点的边，对于行列和为偶数的格子，建立一条从该点到汇点的边，流量均为这个数；对于相邻的格子，建立一条无穷大流量的边，这样要求最大的独立和，我们只要把最小割求出来，总和减去这个最小割就是我们的答案了呢。（EK也不会T哦）

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 555#define Inf 9999999using namespace std;int c[maxn][maxn],tag[maxn],pre[maxn],f[maxn];int a[maxn][maxn];int n,m,s,t,ans,tot,N=99;int Q[maxn],bot,top;void _init(){	s=0,t=n*n+1,ans=tot=0; 	memset(c,0,sizeof c);}void graph(){	for (int i=1; i<=n; i++)		for (int j=1; j<=n; j++)			if ((i+j)%2==1)			{				int cur=i*n+j-n;				c[s][cur]+=a[i][j];				if (i>1) c[cur][cur-n]+=Inf;				if (i<n) c[cur][cur+n]+=Inf;				if (j>1) c[cur][cur-1]+=Inf;				if (j<n) c[cur][cur+1]+=Inf;			}			else c[i*n+j-n][t]+=a[i][j];}int EK(){	N++;	Q[bot=top=1]=s,f[s]=Inf,tag[s]=N;	while (bot<=top)	{		int cur=Q[bot++];		for (int i=s; i<=t; i++)			if (c[cur][i]>0 && tag[i]!=N)			{				tag[i]=N;				pre[i]=cur;				f[i]=min(f[cur],c[cur][i]);				Q[++top]=i;				if (i==t)				{					for (int k=t; k!=s; k=pre[k])						c[pre[k]][k]-=f[t],c[k][pre[k]]+=f[t];					return f[t];				}			}	}	return 0;}int main(){	while (scanf("%d",&n)!=EOF)	{		_init();		for (int i=1; i<=n; i++)			for (int j=1; j<=n; j++) scanf("%d",&a[i][j]),tot+=a[i][j];		graph();		while (int k=EK()) ans+=k;		printf("%d\n",tot-ans);	}	return 0;}

　　


联系
我们