HDU-3047-Zjnu Stadium【带权并查集】题解

川长思鸟来 2021-07-24 20:49 343阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

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:  
（PS： the 5th and 10th requests are incorrect）

### 2.代码 ###

#define _CRT_SECURE_NO_WARNINGS 
    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn = 1e5 + 10;
    int Fa[maxn], Val[maxn];
    void init(int n)
    { 
    	for (int i = 1; i <= n; i++)
    	{ 
    		Fa[i] = i;
    		Val[i] = 0;
    	}
    }
    int find(int x)
    { 
    	if (x != Fa[x])
    	{ 
    		int tmp = Fa[x];
    		Fa[x] = find(Fa[x]);  //路径压缩
    		Val[x] =( Val[tmp] + Val[x])%300;
    	}
    	return Fa[x];
    }
    int main()
    { 
    	int n, m;
    	while (scanf("%d %d",&n,&m)!=EOF)
    	{ 
    		int ans = 0;
    		init(n);
    		while (m--)
    		{ 
    			int a, b, value;
    			scanf("%d %d %d",&a,&b,&value);
    			int x = find(b), y = find(a);
    			if (x == y)
    			{ 
    				if (Val[b] != (Val[a] + value)%300)
    				{ 
    					ans++;
    				}
    			}
    			else
    			{ 
    				Fa[x] = y;
    				Val[x] = (Val[a] + value - Val[b]+300) % 300;
    			}
    		}
    		cout << ans << endl;
    	}
    	return 0;
    }