| ||||||||||
| 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 | |||||||||
这题大家是用并查集作的么?我怎么老是WA啊奇怪,应该没错的啊,大家帮我看看怎么回事啊???
#include <stdio.h>
#include <string.h>
const int maxn=50010;
int fa[maxn],w[maxn];
int N,K,ans;
int find(int ch)
{
if (fa[ch]==0) return ch;
if (fa[fa[ch]]==0) return fa[ch];
fa[ch]=find(fa[ch]);
w[ch]=(w[fa[ch]]+w[ch])%3;
return fa[ch];
}
int main()
{
int D,X,Y,f1,f2;
scanf("%d%d",&N,&K);
ans=0;
memset(fa,0,sizeof(fa));
memset(w,0,sizeof(w));
while (K--){
scanf("%d%d%d",&D,&X,&Y);
if (D==2 && X==Y || X>N || Y>N){
ans++; continue;
}
f1=find(X); f2=find(Y);
if (f1==f2){
if ((w[X]+3-w[Y])%3!=D-1) ans++;
}else{
fa[f1]=f2;
w[f1]=(2-w[X]+w[Y]+D)%3;
}
}
printf("%d\n",ans);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator