HDU 3047 Zjnu Stadium

Zjnu Stadium
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 729    Accepted Submission(s): 297
 
 
Problem Description
In 12th Zhejiang College Students Games 2007, there was a new stadium built in Zhejiang Normal University. It was a modern stadium which could hold thousands of people. The audience Seats made a circle. The total number of columns were 300 numbered 1--300, counted clockwise, we assume the number of rows were infinite.
These days, Busoniya want to hold a large-scale theatrical performance in this stadium. There will be N people go there numbered 1--N. Busoniya has Reserved several seats. To make it funny, he makes M requests for these seats: A B X, which means people numbered B must seat clockwise X distance from people numbered A. For example: A is in column 4th and X is 2, then B must in column 6th (6=4+2).
Now your task is to judge weather the request is correct or not. The rule of your judgement is easy: when a new request has conflicts against the foregoing ones then we define it as incorrect, otherwise it is correct. Please find out all the incorrect requests and count them as R.
 
 
Input
There are many test cases:
For every case: 
The first line has two integer N(1<=N<=50,000), M(0<=M<=100,000),separated by a space.
Then M lines follow, each line has 3 integer A(1<=A<=N), B(1<=B<=N), X(0<=X<300) (A!=B), separated by a space.
 
 
 
Output
For every case: 
Output R, represents the number of incorrect request.
 
 
Sample Input
10 10
1 2 150
3 4 200
1 5 270
2 6 200
6 5 80
4 7 150
8 9 100
4 8 50
1 7 100
9 2 100
 
 
Sample Output
2
Hint
 
Hint:
（PS： the 5th and 10th requests are incorrect）
 
 
 
Source
2009 Multi-University Training Contest 14 - Host by ZJNU
 
 
Recommend
gaojie
解题思路：利用并查集查找两个座位的根节点，将根节点看做参考系原点，根节点相同的话就说明他们可以以同一参考系进行比较，那么根据新输入的数值计算出两个坐标的相对位置，与之前的相对位置冲突的话就是矛盾；根节点不同的话说明两个点的参考系是不同的，但是仅仅是他们的根节点不同使得他们的原点不同，同一参考系下的两点间距离差在换算到另一参考系时不会改变，因此，将后输入的点的参考系原点转化到先输入的前一个点的参考系下，等于将两个参考系合并为一个，原参考系的点在查找的时候会递归更新计算出在新参考系的位置，这样所有点都可以在同一参考系下进行比较。
PS：将原参考系中根节点（原点）位置转化为新参考系中的位置的方法在程序注释中。
[cpp]  
#include<iostream>  
#include<cstring>  
#include<cstdio>  
using namespace std;  
int father[50005],seat[50005],ans;  
void ini()  
{  
    int i;  
    for(i=1;i<50005;i++)  
    {  
        father[i]=i;  
        seat[i]=0;//seat是点的坐标  
    }  
}  
int Find(int x)  
{  
    int temp;  
    if(x==father[x])  
        return x;  
    else  
    {  
        temp=father[x];  
        father[x]=Find(father[x]);  
        seat[x]+=seat[temp];//计算更新到根节点的距离  
        return father[x];  
    }  
}  
void Union(int x,int y,int z)  
{  
    int a,b,tx,ty;  
    a=Find(x);  
    b=Find(y);  
    if(a!=b)  
    {  
        seat[b]=(seat[x]+z+seat[b]-seat[y]);//如果a!=b说明x,y的根节点不同，根节点可以看做一种参照系，seat[x]+z是y在以a为新的根节点下的新参照系中的位置，seat[b]-y是原来以b为根节点的的参照系下(b,y)的距离，这个距离不随参照系改变，因此b在以a为参考系的新位置就是y的新位置加上(b,y)间的距离  
        father[b]=a;  
    }  
    else if(seat[y]!=(seat[x]+z))  
        ans++;  
}  
int main()  
{  
    int a,b,c,i,m,n;  
    while(scanf("%d%d",&m,&n)!=-1)  
    {  
        ans=0;  
        ini();  
        for(i=0;i<n;i++)  
        {  
            scanf("%d%d%d",&a,&b,&c);  
            Union(a,b,c);  
        }  
        printf("%d\n",ans);  
    }  
    return 0;  
}

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