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

这题大家是用并查集作的么?我怎么老是WA啊

Posted by scutacm3 at 2004-10-01 08:13:27 on Problem 1182
奇怪,应该没错的啊,大家帮我看看怎么回事啊???

#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:
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