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;  
}