现在的位置: 首页 > 综合 > 正文

hdu4460

2013年10月30日 ⁄ 综合 ⁄ 共 1875字 ⁄ 字号 评论关闭

/*
分析:
    2012亚洲杭州站H题。
    水题-、-,字典树+松弛,暴力过了。用了字典树,不过据
说更暴力的、不用字典树的,也能ac-、-III

                                                  2011-11-08
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"queue"
using namespace std;
#define N 1011
#define M 10011

int n;
int dis[N];

struct Eage
{
	int from,to;
	int next;
}eage[2*M];
int tot,head[N];
void add(int a,int b)
{
	eage[tot].from=a;
	eage[tot].to=b;
	eage[tot].next=head[a];
	head[a]=tot++;
}

struct dictree
{
	struct dictree *child[52];
	int flag;
};
struct dictree *root;

void insert(char str[],int k)
{
	struct dictree *now,*next;
	int i,l,temp;
	now=root;
	for(i=0;str[i];i++)
	{
		if(str[i]>='a')	temp=str[i]-'a';
		else			temp=str[i]-'A'+26;
		if(now->child[temp]!=NULL)	now=now->child[temp];
		else
		{
			next=(struct dictree *)malloc(sizeof(struct dictree));
			for(l=0;l<52;l++)	next->child[l]=NULL;
			next->flag=-1;
			now->child[temp]=next;
			now=next;
		}
	}
	now->flag=k;
}
int find(char str[])
{
	struct dictree *now;
	int i,temp;
	now=root;
	for(i=0;str[i];i++)
	{
		if(str[i]>='a')	temp=str[i]-'a';
		else			temp=str[i]-'A'+26;
		if(now->child[temp]!=NULL)	now=now->child[temp];
		else	return -1;
	}
	return now->flag;
}
void build()
{
	int m;
	int i,l;
	char str[111],str2[111];
	int f1,f2;

	root=(struct dictree *)malloc(sizeof(struct dictree));
	for(l=0;l<52;l++)	root->child[l]=NULL;
	root->flag=-1;
	for(i=0;i<n;i++)	{scanf("%s",str);insert(str,i);}

	tot=0;
	memset(head,-1,sizeof(head));
	scanf("%d",&m);
	while(m--)
	{
		scanf("%s%s",str,str2);
		f1=find(str);
		f2=find(str2);
		add(f1,f2);
		add(f2,f1);
	}
}
void getdis(int s)
{
	queue<int>q;
	int hash[N];
	int j,v;
	int now,next;
	memset(dis,-1,sizeof(dis));
	memset(hash,0,sizeof(hash));
	dis[s]=0;
	hash[s]=1;
	q.push(s);
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		for(j=head[now];j!=-1;j=eage[j].next)
		{
			v=eage[j].to;
			if(hash[v])	continue;
			hash[v]=1;
			next=v;
			dis[next]=dis[now]+1;
			q.push(next);
		}
	}
}
void solve()
{
	int i,l;
	int ans=0;
	for(i=0;i<n;i++)
	{
		getdis(i);
		for(l=0;l<n;l++)
		{
			if(dis[l]==-1)	{ans=-1;break;}
			ans=ans>dis[l]?ans:dis[l];
		}
		if(ans==-1)	break;
	}
	printf("%d\n",ans);
}
int main()
{
	while(scanf("%d",&n),n)
	{
		build();
		solve();
	}
	return 0;
}

抱歉!评论已关闭.