BZOJ1066: [SCOI2007]蜥蜴

2017-12-03 0 Comments 1,523 Views 0 Times

Time Limit: 1 Sec Memory Limit: 162 MB

Description

　　在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃
到边界外。每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石
柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不
变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个
石柱上。

Input

　　输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱
，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。

Output

　　输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

Sample Input

5 8 2
00000000
02000000
00321100
02000000
00000000
……..
……..
..LLLL..
……..
……..

Sample Output

HINT

100%的数据满足：1<=r, c<=20, 1<=d<=4

Source

Pku 2711 Leapin’ Lizards

Solution

将每个点裂成入点和出点，两个点之间的容量为石柱高度即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=900,M=200000;
int n,m,k,a[25][25];
char s[50];
int DIS(int x1,int y1,int x2,int y2)
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int calc(int x,int y) { return (x-1)*m+y;}
namespace DINIC
{
	int S,T,tot,Next[M],head[N],tree[M],val[M],Queue[N],h[N],cur[N];
	void add(int x,int y,int z)
	{
		tot++;
		Next[tot]=head[x];
		head[x]=tot;
		tree[tot]=y;
		val[tot]=z;
	}
	void add_edge(int x,int y,int z)
	{
		add(x,y,z);
		add(y,x,0);
	}
	bool bfs()
	{
		int t=0,w=1;
		memset(h,-1,sizeof(h));
		Queue[1]=S;h[S]=0;
		while (t!=w)
		{
			int u=Queue[++t];
			for (int i=head[u];i;i=Next[i])
			if (val[i]!=0)
			{
				int v=tree[i];
				if (h[v]==-1)
				{
					Queue[++w]=v;
					h[v]=h[u]+1;
				}
			}
		}
		return h[T]!=-1;
	}
	int dfs(int u,int low)
	{
		if (u==T) return low;
		int used=0;
		for (int i=cur[u];i;i=Next[i])
		{
			cur[u]=i;
			int v=tree[i];
			if (val[i]>0&&h[v]==h[u]+1)
			{
				int w=dfs(v,min(val[i],low-used));
				val[i]-=w;val[i^1]+=w;
				used+=w;
				if (used==low) return low;
			}
		}
		if (used==0) h[u]=-1;
		return used;
	}
	int dinic()
	{
		int ans=0;
		while (bfs())
		{
			for (int i=1;i<=T;i++) cur[i]=head[i];
			ans+=dfs(S,1<<29);
		}
		return ans;
	}
}
int main()
{
	using namespace DINIC;
	scanf("%d%d%d",&n,&m,&k);
	tot=1;
	S=n*m*2+1;T=n*m*2+2;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++) scanf("%1d",&a[i][j]);
	int Ans=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for (int j=1;j<=m;j++)
			if (s[j]=='L') add_edge(S,calc(i,j)+n*m,1),Ans++;
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		if (a[i][j]>0)
		{
			add_edge(calc(i,j)+n*m,calc(i,j),a[i][j]);
			for (int x=1;x<=n;x++)
				for (int y=1;y<=m;y++)
				if (a[x][y]>0&&(x!=i||y!=j)&&DIS(i,j,x,y)<=k*k) add_edge(calc(i,j),calc(x,y)+n*m,1<<29);
			if (DIS(i,j,0,j)<=k*k||DIS(i,j,i,0)<=k*k||DIS(i,j,i,m+1)<=k*k||DIS(i,j,n+1,j)<=k*k)
				add_edge(calc(i,j),T,1<<29);
		}
	printf("%d\n",Ans-dinic());
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

const int N=900,M=200000;

int n,m,k,a[25][25];

char s[50];

int DIS(int x1,int y1,int x2,int y2)

{

return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);

}

int calc(int x,int y) { return (x-1)*m+y;}

namespace DINIC

{

int S,T,tot,Next[M],head[N],tree[M],val[M],Queue[N],h[N],cur[N];

void add(int x,int y,int z)

{

tot++;

Next[tot]=head[x];

head[x]=tot;

tree[tot]=y;

val[tot]=z;

}

void add_edge(int x,int y,int z)

{

add(x,y,z);

add(y,x,0);

}

bool bfs()

{

int t=0,w=1;

memset(h,-1,sizeof(h));

Queue[1]=S;h[S]=0;

while (t!=w)

{

int u=Queue[++t];

for (int i=head[u];i;i=Next[i])

if (val[i]!=0)

{

int v=tree[i];

if (h[v]==-1)

{

Queue[++w]=v;

h[v]=h[u]+1;

}

return h[T]!=-1;

}

int dfs(int u,int low)

{

if (u==T) return low;

int used=0;

for (int i=cur[u];i;i=Next[i])

{

cur[u]=i;

int v=tree[i];

if (val[i]>0&&h[v]==h[u]+1)

{

int w=dfs(v,min(val[i],low-used));

val[i]-=w;val[i^1]+=w;

used+=w;

if (used==low) return low;

}

if (used==0) h[u]=-1;

return used;

}

int dinic()

{

int ans=0;

while (bfs())

{

for (int i=1;i<=T;i++) cur[i]=head[i];

ans+=dfs(S,1<<29);

}

return ans;

}

int main()

{

using namespace DINIC;

scanf("%d%d%d",&n,&m,&k);

tot=1;

S=n*m*2+1;T=n*m*2+2;

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

for (int j=1;j<=m;j++) scanf("%1d",&a[i][j]);

int Ans=0;

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

{

scanf("%s",s+1);

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

if (s[j]=='L') add_edge(S,calc(i,j)+n*m,1),Ans++;

}

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

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

if (a[i][j]>0)

{

add_edge(calc(i,j)+n*m,calc(i,j),a[i][j]);

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

for (int y=1;y<=m;y++)

if (a[x][y]>0&&(x!=i||y!=j)&&DIS(i,j,x,y)<=k*k) add_edge(calc(i,j),calc(x,y)+n*m,1<<29);

if (DIS(i,j,0,j)<=k*k||DIS(i,j,i,0)<=k*k||DIS(i,j,i,m+1)<=k*k||DIS(i,j,n+1,j)<=k*k)

add_edge(calc(i,j),T,1<<29);

}

printf("%d\n",Ans-dinic());

return 0;

}

He Kai's blog

BZOJ1066: [SCOI2007]蜥蜴

Description

Input

Output

Sample Input

Sample Output

HINT

Source

Solution

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

发表评论取消回复

Description

Input

Output

Sample Input

Sample Output

HINT

Source

Solution

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

发表评论 取消回复

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

发表评论取消回复