1612.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"

int dis[50][50],n;

void init()
{
	char c;
	int i,j,k;
	
	cin>>n;


	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			dis[i][j]=9999;
		dis[i][i]=0;
	}
	
	for(i=0;i<n;i++)
	{
		cin.get(c);
		while(cin.peek()!='\n')
		{
			cin>>j;
			
			dis[i][j-1]=1;
			dis[j-1][i]=1;
		}
		
	}
    
    for(k=0;k<n;k++)
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	if(dis[i][k]<9999&&dis[k][j]<9999&&dis[i][k]+dis[k][j]<dis[i][j])
		dis[i][j]=dis[i][k]+dis[k][j];

}

void doit()
{
	int m,v[100],i,j,d,k;
	bool sign[100];
	char c;

	cin>>m;

	while(m--)
	{
		for(i=0;i<n;i++)
			sign[i]=0;
		
		i=0;
		if(cin.peek()=='\n')
			cin.get(c);
		while(cin.peek()!='\n')
		{
			cin>>v[i];
			if(cin.fail())break;
			v[i]--;
			
			if(v[i]<n&&sign[v[i]]==0)
			{
				sign[v[i]]=1;
				i++;
			}
			
		}
		d=i;



		for(i=0;i<n;i++)
		{
			for(j=0;j<d&&sign[i]==0;j++)
			for(k=0;k<d;k++)
				if(dis[v[j]][i]+dis[i][v[k]]==dis[v[j]][v[k]]&&dis[v[j]][v[k]]<9999)
				{
					sign[i]=1;
					break;
				}
		}

		for(i=0;i<n;i++)
			if(!sign[i])break;

		if(i>=n)cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
	
}

int main()
{
	init();
	doit();
	return 0;
}