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

求救,找不到错误了,内附代码。给几组数据也行。谢谢了。

Posted by 22220000 at 2010-04-01 12:32:31 on Problem 2827
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=21000;
int father[MAX],rank[MAX],ma[MAX*2];
struct ss
{
	int x,y,v;
};
ss node[MAX];
int N,num;
void Input()
{
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].v);
		ma[i*2-1]=node[i].x;
		ma[i*2]=node[i].y;
	}
	sort(ma+1,ma+1+2*N);//离散化 
	num=1;
	for(int i=2;i<=2*N;i++)
		if(ma[num]!=ma[i])
			ma[++num]=ma[i];
}
int Search(int x)//二分查找 
{
	int left=1,right=num,mid;
	while(left<=right)
	{
		mid=(left+right)/2;
		if(ma[mid]==x) return mid;
		else if(ma[mid]>x) right=mid-1;
		else left=mid+1;
	}
}
void Initial()//初始化 
{
	for(int i=0;i<=num;i++)
	{
		rank[i]=0;
		father[i]=i;
	}
}
int Find_Father(int x)//查找根节点 
{
	if(x!=father[x])
	{
		int t=father[x];
		father[x]=Find_Father(t);
		rank[x]+=rank[t];
		return father[x];
	}
	return father[x];
}
void Union(int x,int y,int d)//合并 
{
	int xx=Find_Father(x);
	int yy=Find_Father(y);
	if(xx<yy)//小的为根 
	{
		father[yy]=xx;
		rank[yy]=rank[x]+d-rank[y];
	}
	else
	{
		father[xx]=yy;
		rank[xx]=rank[y]+d-rank[x];
	}
}
void Solve()
{
	for(int i=1;i<=N;i++)
	{
		if(node[i].x>node[i].y) {swap(node[i].x,node[i].y);}
		int x=Search(node[i].x)-1,y=Search(node[i].y);
		if(Find_Father(x)!=Find_Father(y))//不在同一棵树上 
		{
			Union(x,y,node[i].v);
			printf("Accept\n");
		}
		else//在同一个根上 
		{
			if(rank[y]-rank[x]==node[i].v)
				printf("Accept\n");
			else
				printf("Bug Detected %d\n",rank[y]-rank[x]);
		}
	}
}
int main()
{
	while(scanf("%d",&N)!=EOF)
	{
		Input();
		Initial();
		Solve();
	}
}

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