HDU1569 方格取数(2)
? 解题记录 ? ? HDU ? ? 最大流 ? ? 补档计划第一期 ? ? 网络流 ?    2017-10-01 13:58:27    546    1    0

 

给你一个m*n的格子的棋盘,每个格子里面有一个非负数。 
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取数所在的2个格子不能相邻,并且取出的数的和最大。

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;
}

 

上一篇: 洛谷P3384 【模板】树链剖分

下一篇: SPOJ1812 Longest Common Substring II

546 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航