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