| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求救,找不到错误了,内附代码。给几组数据也行。谢谢了。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator