hdu 3038 How Many Answers Are Wrong（带权并查集）

10 51 10 1007 10 281 3 324 6 416 6 1 Sample Output
1ps：简单的带权并查集，因为有d(i,j]+d(j,k]=d(i,k]，所以只需要把a,b,k看成是a-1到b的距离为k，       这样的话，所有的数据都可以通过到根节点的距离联系起来，接着判断一下就好了。代码：
#include<stdio.h>#include<stdlib.h>#include<string.h>#define maxn 200000+10int pre[maxn],rank[maxn];//rank[]表示到根节点的距离int n,m,sum;void init(){    for(int i=0; i<=n; i++)    {        pre[i]=i;        rank[i]=0;    }    sum=0;}int Find(int x){    int temp=pre[x];    if(x==pre[x])        return x;    pre[x]=Find(temp);    rank[x]=rank[x]+rank[temp];    return pre[x];}void join(int x,int y,int k){    int fx=Find(x),fy=Find(y);    if(fx!=fy)    {        pre[fx]=fy;        rank[fx]=rank[y]+k-rank[x];    }    else    {        if(rank[x]-rank[y]!=k)            sum++;    }}int main(){    while(~scanf("%d%d",&n,&m))    {        init();        int x,y,z,i;        for(i=1; i<=m; i++)        {            scanf("%d%d%d",&x,&y,&z);            join(x-1,y,z);        }        printf("%d/n",sum);    }    return 0;}