「BZOJ2595」[Wc2008] 游览计划

2014年12月20日7,0144

Description

Input

第一行有两个整数，N和 M，描述方块的数目。
接下来 N行，每行有 M 个非负整数，如果该整数为 0，则该方块为一个景点；
否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，
行首行末也可能有多余的空格。

Output

由 N + 1行组成。第一行为一个整数，表示你所给出的方案
中安排的志愿者总数目。
接下来 N行，每行M 个字符，描述方案中相应方块的情况：
z ‘_’（下划线）表示该方块没有安排志愿者；
z ‘o’（小写英文字母o）表示该方块安排了志愿者；
z ‘x’（小写英文字母x）表示该方块是一个景点；
注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不
一致（任何一行中，多余的空格都不允许出现），都可能导致该测试点不得分。

Sample Input

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

Sample Output

6
xoox
___o
___o
xoox

HINT

对于100%的数据，N,M,K≤10，其中K为景点的数目。输入的所有整数均在[0,2^16]的范围内

题解

斯坦纳树

大家一起orz zky吧

http://blog.csdn.net/iamzky/article/details/42029921

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<queue>
#define pa pair<int,int>
#define ll long long
#define inf 100000000
using namespace std;
int read()
{
	int x=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
int a[15][15];
int bin[20];
int n,m,K;
int f[12][12][1024];
struct data{
	int fit,sed,thd;
}pre[15][15][1024];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
queue<pa>q;
bool inq[15][15],vis[15][15];
void spfa(int sta)
{
	while(!q.empty())
	{
		int x=q.front().first,y=q.front().second;
		inq[x][y]=0;q.pop();
		for(int k=0;k<4;k++)
		{
			int nowx=x+xx[k],nowy=y+yy[k];
			if(x<1||y<1||x>n||y>m)continue;
			if(f[nowx][nowy][sta]>f[x][y][sta]+a[nowx][nowy])
			{
				f[nowx][nowy][sta]=f[x][y][sta]+a[nowx][nowy];
				pre[nowx][nowy][sta]=(data){x,y,sta};
				if(!inq[nowx][nowy])
				{
					q.push(make_pair(nowx,nowy));
					inq[nowx][nowy]=1;
				}
			}
		}
	}
}
void dfs(int x,int y,int sta)
{
	if(x>inf||pre[x][y][sta].thd==0)return;
	vis[x][y]=1;
	data t=pre[x][y][sta];
	dfs(t.fit,t.sed,t.thd);
	if(t.fit==x&&t.sed==y)dfs(x,y,sta-t.thd);
}
int main()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	n=read();m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			a[i][j]=read();
			if(!a[i][j])K++;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<bin[K];k++)
				f[i][j][k]=pre[i][j][k].fit=inf;
	K=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!a[i][j])
				f[i][j][bin[K]]=0,K++;
	for(int sta=1;sta<bin[K];sta++)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				for(int s=sta&(sta-1);s;s=sta&(s-1))
				{
					int t=f[i][j][s]+f[i][j][sta-s]-a[i][j];
					if(t<f[i][j][sta])
					{
						f[i][j][sta]=t;
						pre[i][j][sta]=(data){i,j,s};
					}
				}
				if(f[i][j][sta]<inf)
					q.push(make_pair(i,j)),inq[i][j]=1;
			}spfa(sta);
	}
	int x,y;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!a[i][j])
			{
				x=i;y=j;break;
			}
	dfs(x,y,bin[K]-1);
	printf("%d\n",f[x][y][bin[K]-1]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(!a[i][j])printf("x");
			else if(vis[i][j])printf("o");
			else printf("_");
		}
		puts("");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<queue>

#define pa pair<int,int>

#define ll long long

#define inf 100000000

using namespace std;

int read()

{

int x=0;char ch=getchar();

while(ch>'9'||ch<'0')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int a[15][15];

int bin[20];

int n,m,K;

int f[12][12][1024];

struct data{

int fit,sed,thd;

}pre[15][15][1024];

int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};

queue<pa>q;

bool inq[15][15],vis[15][15];

void spfa(int sta)

{

while(!q.empty())

{

int x=q.front().first,y=q.front().second;

inq[x][y]=0;q.pop();

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

{

int nowx=x+xx[k],nowy=y+yy[k];

if(x<1||y<1||x>n||y>m)continue;

if(f[nowx][nowy][sta]>f[x][y][sta]+a[nowx][nowy])

{

f[nowx][nowy][sta]=f[x][y][sta]+a[nowx][nowy];

pre[nowx][nowy][sta]=(data){x,y,sta};

if(!inq[nowx][nowy])

{

q.push(make_pair(nowx,nowy));

inq[nowx][nowy]=1;

}

void dfs(int x,int y,int sta)

{

if(x>inf||pre[x][y][sta].thd==0)return;

vis[x][y]=1;

data t=pre[x][y][sta];

dfs(t.fit,t.sed,t.thd);

if(t.fit==x&&t.sed==y)dfs(x,y,sta-t.thd);

}

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

n=read();m=read();

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

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

{

a[i][j]=read();

if(!a[i][j])K++;

}

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

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

for(int k=0;k<bin[K];k++)

f[i][j][k]=pre[i][j][k].fit=inf;

K=0;

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

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

if(!a[i][j])

f[i][j][bin[K]]=0,K++;

for(int sta=1;sta<bin[K];sta++)

{

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

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

{

for(int s=sta&(sta-1);s;s=sta&(s-1))

{

int t=f[i][j][s]+f[i][j][sta-s]-a[i][j];

if(t<f[i][j][sta])

{

f[i][j][sta]=t;

pre[i][j][sta]=(data){i,j,s};

}

if(f[i][j][sta]<inf)

q.push(make_pair(i,j)),inq[i][j]=1;

}spfa(sta);

}

int x,y;

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

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

if(!a[i][j])

{

x=i;y=j;break;

}

dfs(x,y,bin[K]-1);

printf("%d\n",f[x][y][bin[K]-1]);

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

{

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

{

if(!a[i][j])printf("x");

else if(vis[i][j])printf("o");

else printf("_");

}

puts("");

}

return 0;

}

« 「BZOJ1226」[SDOI2009] 学校食堂Dining 「POJ2404」Jogging Trails »

广大圆明

另外第52行的那个x>inf应该是x>=inf

广大圆明

黄学长的第36行的那个程序应该把x改成nowx，y改成nowy吧，我纯口胡。。。

ez_zjt

扑通扑通跪下来，千古神犇黄哲威

wyh_ct_681

发现看着学长的博客，受益匪浅，orz zky

hzwer.com _ Home | http://hzwer.com

「BZOJ2595」[Wc2008] 游览计划

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论