Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

感觉测试数据不仅仅是有空格,而且应该是有102个点

Posted by lanmao45 at 2014-05-31 13:48:26 on Problem 3026
我用liantong数组标记两个点是否已经相连,之前开到102死都过不了,不停wa,改了许久之后还是过不了,只好作死的加大各个数组的范围,结果突然就过了,发现只要把liantong开到103*103即可,那么就应该是有102个可联通的点才会出现这种情况才对。
我的代码:
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
using namespace std;
int map[52][52],father[102],liantong[103][103];
struct n1
{
	int x,y,step;
};
n1 dian[102];
n1 path[6000];
int bfs(int i,int k,int row,int line)
{
	n1 temp1,temp2;
	queue<n1>q1;
	int vis[52][52],j;
	memset(vis,0,sizeof(vis));
	temp1=dian[i];
	temp1.step=0;
	q1.push(temp1);
	vis[temp1.x][temp1.y]=1;
	while(q1.size()!=0)
	{
		temp1=q1.front();
		q1.pop();
		for(j=1;j<=4;j++)
		{
			temp2=temp1;
			temp2.step++;
			if(j==1)
			temp2.x--;
			else if(j==2)
			temp2.x++;
			else if(j==3)
			temp2.y--;
			else
			temp2.y++;
			if(map[temp2.x][temp2.y]!=0&&vis[temp2.x][temp2.y]==0&&liantong[i][map[temp2.x][temp2.y]]==0)
			{
				q1.push(temp2);
				vis[temp2.x][temp2.y]=1;
				if(map[temp2.x][temp2.y]>0)
				{
					k++;
					path[k].x=i;
					path[k].y=map[temp2.x][temp2.y];
					path[k].step=temp2.step;
					liantong[i][map[temp2.x][temp2.y]]=liantong[map[temp2.x][temp2.y]][i]=1;
				}
			}
		}
	}
	return k;
}
int find(int i)
{
	while(i!=father[i])
	i=father[i];
	return i;
}
int cmp(n1 a,n1 b)
{
	return a.step<b.step;
}
int kruskal(int v,int e)
{
	int temp1,temp2,i,num_bian,sum;
	for(i=1;i<=v;i++)
	father[i]=i;
	sort(path+1,path+1+e,cmp);
	sum=num_bian=0;
	v--;
	for(i=1;num_bian<v;i++)
	{
		temp1=find(path[i].x);
		temp2=find(path[i].y);
		if(temp1!=temp2)
		{
			num_bian++;
			sum+=path[i].step;
			if(temp1>temp2)
			temp1^=temp2^=temp1^=temp2;
			father[temp2]=temp1;
		}
	}
	return sum;
}
int main()
{
	int i,n,line,row,j,k;
	char data[52][52],temp[1000];
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&line,&row);
		gets(temp);
		for(i=0;i<row;i++)
		gets(data[i]);
		k=0;
		memset(map,0,sizeof(map));
		for(i=0;i<row;i++)
		for(j=0;j<line;j++)
		{
			if(data[i][j]=='A'||data[i][j]=='S')
			{
				map[i+1][j+1]=++k;
				dian[k].x=i+1;
				dian[k].y=j+1;
			}
			else if(data[i][j]==' ')
			map[i+1][j+1]=-1;
		}
		int bian=0;
		memset(liantong,0,sizeof(liantong));
		for(i=1;i<=k;i++)
		bian=bfs(i,bian,row,line);
		printf("%d\n",kruskal(k,bian));
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator