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

HELP!! 貌似测试数据都过了 可就老WA

Posted by BGW991111 at 2010-06-10 13:50:19 on Problem 2492
#include<iostream>
using namespace std;
int find(int x);
void bing(int fa,int fb,int a,int b);
int father[3003],du[3003];
bool sex[3003];
int main(void)
{
	int w,n,i,num,in,a,b,fa,fb,q;
	cin>>n;
	for(w=1;w<=n;w++)
	{
		scanf("%d%d",&num,&in);
		for(i=1;i<=num;i++)
		{
			father[i]=i;
			du[i]=1;  //深度
			sex[i]=false;   //false代表与头结点性别一致,true代表不同
		}
		q=0;
		while(in--)
		{
			scanf("%d%d",&a,&b);
			if(q==0)
			{
				fa=find(a);
				fb=find(b);
				if(fa!=fb)
				{	
					bing(fa,fb,a,b);
				}
				else
				{
					if(sex[a]==sex[b])
					{
						q=1;
					}
				}
			}		
		}
		if(in==-1&&q==0)
		{
			cout<<"Scenario #"<<w<<":"<<endl;
			cout<<"No suspicious bugs found!"<<endl<<endl;
		}
		else
		{
			cout<<"Scenario #"<<w<<":"<<endl;
			cout<<"Suspicious bugs found!"<<endl<<endl;
		}
	}
	return 0;
}
int find(int x)  //不带压缩路劲  为了更新各结点性别方便
{
	int k;
	k=x;
	if(x!=father[x])
	{
		k=find(father[x]);
		sex[x]=!sex[k];	   //从头结点(father结点)开始,以头结点为准更新以下的结点的性别
	}	
	return k;
}
void bing(int fa,int fb,int a,int b)
{
	if(du[fa]>du[fb])
	{
		father[fb]=fa;	
		sex[fb]=!(sex[a]^sex[b]);  //更新性别
	}
	else
	{
		father[fa]=fb;
		sex[fa]=!(sex[a]^sex[b]);
	}
	if(du[fa]==du[fb])
	{
		du[fb]=du[fb]+1;
	}
}

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