Zjnu Stadium(hdu3047带权并查集)

题意：一个300列的无限行的循环场地，a b d代表a,b顺时针相距d的距离，现在给你一些距离，判断是否有冲突，如果有冲突计算冲突的次数

思路：带权并查集

a，b的距离等于b到根节点的距离 - a到根节点的距离

1.当a,b在同一集合的时候就用b到根节点的距离 - a到根节点的距离和当前输入的距离进行对比，看是否满足条件

2.当a,b不在同一集合的时候合并两个节点，更新距离

向量法，方向一定要搞清楚，父亲指向儿子

如果x的父亲rootx ，y的父亲是rooty

rootx --> x, rooty --> y合并的方向是rootx的父亲是rooty 即rooty --> rootx

x --> y的距离是d

rooty --> rootx = rootx --> x + x --> y + y --> rooty = rootx --> x +(-( y --> x ) ) + (-( rooty -->y))

合并的方向不同式子也不同


 #include<iostream>   
#include<cstdio>   
#include<cstring>   
#include<algorithm>   
using namespace std;  
int flag = 0;  
struct bian  
{  
    int father;  
    int dis;  
}p[50050];  
  
void Make_set(int n)  
{  
    int i;  
    for(i = 1; i <= n; i++)  
    {  
        p[i].father = i;  
        p[i].dis = 0;  
    }  
}  
  
int Find_set(int x)  
{  
    if(x != p[x].father)  
    {  
        int temp = p[x].father;  
        p[x].father = Find_set(p[x].father);  
        p[x].dis = ( p[x].dis + p[temp].dis) % 300;  
    }  
    return p[x].father;  
}  
  
void Union(int a,int b,int d)  
{  
    int x = Find_set(a);  
    int y = Find_set(b);  
    if(x == y)  
    {  
        if(( (p[b].dis-p[a].dis+300) % 300 ) != d)  
        {  
            flag = 1;  
            return ;  
        }  
    }  
    else  
    {  
        p[x].father = y;  
        p[x].dis = (p[b].dis+300-d-p[a].dis) % 300;  
    }  
}  
int main()  
{  
    int n,m;  
    while(scanf("%d%d",&n,&m) != EOF)  
    {  
        int i,sum = 0;  
        Make_set(n);  
        for(i = 0; i < m; i++)  
        {  
            int a,b,d;  
            flag = 0;  
            scanf("%d%d%d",&a,&b,&d);  
            Union(a,b,d);  
            if(flag)  
                sum++;  
        }  
        printf("%d\n",sum);  
    }   
    return 0;  
}

补充：软件开发 , C++ ,