#include<stdio.h>
#include<algorithm>
using namespace std;

typedef struct{
	int x,y,l;
}seq;

seq s[10010];
int list[20010],n,m;
int sum[20010];
int father[20010];

int Input()
{
	int i;

	if(scanf("%d",&m)==EOF)return 0;

	list[0]=0;
	n=1;
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].l);
		list[n++]=s[i].x;//作映射用的
		list[n++]=s[i].y;
	}
	return 1;
}

int cmp(const int &a,const int &b)
{
	return a<b;
}

void SortList()
{
	int i,j;

	sort(list,list+n,cmp);

	j=0;
	for(i=1;i<n;i++)    //去掉list[]中相同的数
		if(list[i]!=list[j])
			list[++j]=list[i];
	n=j;
}

void InitSet()
{
	int i;

	for(i=0;i<=n;i++)
	{
		father[i]=i;
		sum[i]=0;
	}
}

int Map(int num,int l,int r)//二分查找
{
	int mid;

	mid=(l+r)/2;
	if(list[mid]==num)return mid;
	else if(list[mid]>num)return Map(num,l,mid-1);
	else return Map(num,mid+1,r);
}

int FindRoot(int p)
{
	int b=father[p];

	if(father[p]!=p)
	{
		father[p]=FindRoot(father[p]);
		sum[p]+=sum[b];   //刷新路径压缩后的sum(p+1,father[p])
	}
	return father[p];
}

int Accept(int p,int q,int l,int &result)
{
	int a,b;

	a=FindRoot(p);
	b=FindRoot(q);         /*printf("a=%d b=%d\n",a,b);*/

	if(a==b)
	{
		result=sum[p]-sum[q];
		if(result!=l)return 0;
		else return 1;
	}

	if(a>b)   //总是以较大的根作为两集合合并后的根
	{
		father[b]=a;
		sum[b]=sum[p]-sum[q]-l;
	}
	else
	{
		father[a]=b;
		sum[a]=sum[q]+l-sum[p];
	}
	return 1;
}

void Swap(int &p,int &q)
{
	int t;
	t=p;p=q;q=t;
}

void Ans()
{
	int i,p,q,result;

	SortList();

	InitSet();

	for(i=0;i<m;i++)
	{
		p=Map(s[i].x,0,n); //将s[i].x映射到升序序列list[]中s[i].x所在位置
		q=Map(s[i].y,0,n);
		if(p>q)Swap(p,q);

		/*printf("p=%d q=%d l=%d\n",p,q,s[i].l);*/

		if(Accept(p-1,q,s[i].l,result))printf("Accept\n");
		else printf("Bug Detected %d\n",result);		
	}
}

int main()
{
	while(Input())
		Ans();

	return 0;
} 

• Re:求助！！！给两组数据也好啊.......谢了 (0) me 2006-06-14 16:08:29