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

通过我的错误,贡献一组数据:1 2 1 3 1 4 1 5 0 0 这是树

Posted by Pzjay at 2009-10-15 22:36:34 on Problem 1308
In Reply To:天啦,给偶块豆腐让偶去撞死吧,大牛请来相帮 Posted by:Pzjay at 2009-10-15 16:48:25
> 6 8  5 3  5 2  6 4
> 5 6  0 0
> Case 1 is a tree.
> 
> 8 1  7 3  6 2  8 9  7 5
> 7 4  7 8  7 6  0 0
> Case 2 is a tree.
> 
> 3 8  6 8  6 4
> 5 3  5 6  5 2  0 0
> Case 3 is not a tree.
> 0 0
> Case 4 is a tree.
> 
> 1 1 0 0
> Case 5 is not a tree.
> 
> 1 2 1 2 0 0
> Case 6 is not a tree.
> 
> 1 2 2 3 4 5 0 0
> Case 7 is not a tree.
> 
> 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 0 0
> Case 8 is not a tree.
> 
> 1 2 2 1 0 0
> Case 9 is not a tree.
> 
> 1 2 2 3 3 1 5 6 0 0
> Case 10 is not a tree.
> -1 -1
> 请按任意键继续. . .
> 
> 
> 目前已知所有测试数据都过了,竟然还WA!!!这个T会卡RP的么???码子搁这,看那位大牛能检查出问题来:
> #include<iostream>
> #include<cstring>
> #include<queue>
> #include<set>
> using namespace std;
> const int nax=1000;
> int a[nax],b[nax],c[nax];
> bool matrix[nax/10][nax/10];
> int sum;//点的个数
> void bfs(int a)
> {
> 	queue<int>q;
> 	int tmp,i;
> 	q.push(a);
> 	while(!q.empty())
> 	{
> 		tmp=q.front();
> 		q.pop();
> 		for(i=0;i<sum;++i)
> 		{
> 			if(matrix[tmp][i])
> 			{
> 				matrix[tmp][i]=false;
> 				q.push(i);
> 			}
> 		}
> 	}
> }
> int main()
> {
> 	int edge;
> 	set<int>pzj;
> 	int m,n;
> 	bool is,ak;
> 	int root;//记录根节点
> 	int k=0,i,j;
> 	while(true)
> 	{
> 		sum=0;
> 		memset(matrix,false,sizeof(matrix));
> 		ak=true;
> 		pzj.clear();
> 		edge=0;
> 		is=true;
> 		i=0;
> 		memset(a,0,sizeof(a));
> 		memset(b,0,sizeof(b));
> 		memset(c,0,sizeof(c));
> 		scanf("%d%d",&m,&n);
> 		if(m==-1 && n==-1)
> 			break;
> 		if((m+n)==0)
> 		{
> 			printf("Case %d is a tree.\n",++k);
> 			continue;
> 		}
> 		matrix[m][n]=true;
> 		edge++;
> 		pzj.insert(m);
> 		pzj.insert(n);
> 		c[m]++;
> 		b[n]++;
> 		while(scanf("%d%d",&m,&n) && (m+n))
> 		{
> 			matrix[m][n]=true;
> 			edge++;
> 			pzj.insert(m);
> 			pzj.insert(n);
> 			c[m]++;
> 			if(c[m]==1)
> 				a[i++]=m;//保存父节点并防止重复保存
> 			b[n]++;
> 			if(b[n]>1)//出现入度大于1
> 				is=false;
> 		}
> 		if(!is)
> 		{
> 			printf("Case %d is not a tree.\n",++k);
> 			continue;
> 		}//满足没有节点入度大于1
> 		int cou=0;
> 		if(pzj.size()-1!=edge)
> 		{
> 			printf("Case %d is not a tree.\n",++k);
> 			continue;
> 		}
> 		else//满足点边关系
> 		{
> 			for(j=0;j<i;j++)
> 				if(b[a[j]]==0)
> 				{
> 					cou++;
> 					root=a[j];
> 				}
> 		}
> 		if(cou==1)//满足只有一个根的条件
> 		{
> 			sum=pzj.size();//点的个数
> 			bfs(root);//判断有无环的情况
> 			for(i=0;i<sum;++i)
> 				for(j=0;j<sum;++j)
> 					if(matrix[i][j])
> 						goto hoho;
> 				printf("Case %d is a tree.\n",++k);
> 		}
> 
> 		else
> hoho:			printf("Case %d is not a tree.\n",++k);
> 
> 	}
> 	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