Tyvj-1338 QQ农场

P1338 QQ农场

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

Sandytea前段时间沉迷于QQ农场中……一天夜里，他梦见来到好友X的农场上……

描述

这个农场和游戏中略有不同。土地实际上是一个边长为N的正方形，由N*N块土地组成。
在每块土地上，都种有一种农作物。如果他选择摘取一块土地上的农作物，就能获得一个固定的利润(当然，这个利润是正数)。不同土地上的利润多半是不同的。
贪心的Sandytea本想摘取所有土地上的农作物。但是正当他准备行动时，却被告知不允许摘取了两块有公共边的土地上的作物，否则就会被主人的狗发现。
Sandytea想知道，在不被狗抓住的前提下，他能获得的最大利益是多少。

输入格式

第一行：一个整数N，表示土地是一个边长为N的正方形。
下面N行：每行N个正整数，描述了各块土地上的农作物的单位价值。

输出格式

输出一行，包含一个整数，为最大的收益。

测试样例1

输入

2
7 7
54 54

输出

61

备注

数据范围：
有10分的数据满足：N≤6
另有20分的数据满足：N≤13
另有30分的数据满足：N≤50
另有40分的数据满足：N≤200
所有数据满足：每块土地上作物的价值不超过100。改编自SPOJ

题解：

把格子交替染成不同颜色（即分成两部分），这样相邻的格子颜色不同，就转化成了一个二分图匹配的问题。源点s向每个白格子连流量等于土地价值的边，黑格子向汇点t连，黑白格子之间连流量为inf的边，求最小割。

注意不要把边建重了。由于每个黑格子可能会被重复连，所以不应该在每次连黑白格子之间的边时，连黑格子到t的边

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#define nn 40010                 //因为是矩形，所以要n*n

#define mm 1000010

#define inf 2000000001

using namespace std;

int get()

{

	int ans=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)) {ans=ans*10+ch-'0';ch=getchar();}

	return ans*f;

}

int x[4]={1,-1,0,0},y[4]={0,0,1,-1};

int e=0,n,ss,tt,fir[nn],nxt[mm],to[mm],flow[mm],q[nn],dep[nn],f[210][210];

void add(int a,int b,int c)

{

	nxt[++e]=fir[a];fir[a]=e;to[e]=b;flow[e]=c;

	nxt[++e]=fir[b];fir[b]=e;to[e]=a;flow[e]=0;

}

bool il(int x,int y)

{

	if(x>0&&x<=n&&y>0&&y<=n) return 1;return 0;

}

bool bfs()

{

	int h=1,t=1,o;

	q[1]=ss;

	while(h<=t)

	  {

	  	o=q[h++];

	  	for(int i=fir[o];i;i=nxt[i])

	  	  if(flow[i]&&!dep[to[i]])

	  	    {

	  	    	dep[to[i]]=dep[o]+1;

	  	    	q[++t]=to[i];

			}

	  }

	if(dep[tt]) return 1;

	return 0;

}

int maxflow(int s,int f)

{

	if(!f||s==tt) return f;         //写成了return 0

	int newflow,newans=0;

	for(int i=fir[s];i;i=nxt[i])

	  if(dep[to[i]]==dep[s]+1&&flow[i])

	    {

	    	newflow=maxflow(to[i],min(f,flow[i]));            //流量要和flow[i]取min

	    	f-=newflow;

	    	flow[i]-=newflow;

	    	flow[((i-1)^1)+1]+=newflow;

	    	newans+=newflow;

	    	if(!f) break;

		}

	if(f>0)

	  dep[s]=-1;                    //神奇的优化

	return newans;

}

int main()

{

    n=get();ss=0,tt=n*n+1;

	int ans=0;

	for(int i=1;i<=n;i++)

	  for(int j=1;j<=n;j++)

	    {

	    	f[i][j]=get();

	    	ans+=f[i][j];

		}

	for(int i=1;i<=n;i++)

	  for(int j=1;j<=n;j++)

	    if((i+j)%2)

	    {

		    add(ss,(i-1)*n+j,f[i][j]);         //开始写到下一个for里面了，然后就加重了

	    	for(int k=0;k<4;k++)

	          if(il(i+x[k],j+y[k]))

	            add((i-1)*n+j,(i+x[k]-1)*n+j+y[k],inf);            //一开始在这里加了到tt的边，然后就加重了

		}

	    else

	      add((i-1)*n+j,tt,f[i][j]);

	dep[ss]=1;

	while(bfs())

	  {

	  	ans-=maxflow(ss,inf);

	  	for(int i=1;i<=tt;i++)         //算上ss、tt

	  	  dep[i]=0;

	  	dep[ss]=1;

	  }

	printf("%d",ans);

	return 0;

}

/*

3

3 42 26

81 26 36

68 52 71

6

76 53 11 42 48 27

19 78 74 46 22 57

14 2 33 62 15 62

23 62 39 95 91 69

45 36 62 44 91 70

10 7 97 67 66 68

*/

巴特西

Tyvj-1338 QQ农场

背景

描述

输入格式

输出格式

测试样例1

输入

输出

备注

题解：

最新文章

热门文章