## Zjnu Stadium

- Time Limit: 2000/1000 MS (Java/Others)
- Memory Limit: 32768/32768 K (Java/Others)
- Total Submission(s): 4730
- Accepted Submission(s): 1822

### 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

PS： the 5th and 10th requests are incorrect

### Source

2009 Multi-University Training Contest 14 - Host by ZJNU

### Recommend

gaojie

### 链接

http://acm.hdu.edu.cn/showproblem.php?pid=3047

### 题意

体育馆的座位布局为圆环形，总共由300列组成，行数不限。现有一个规则：A B X，表明A和B之间必须相差X列。共有n个人和m组判断，问有多少组判断是错误的。

### 题解

只需要用一个数组sum[x]记录x与其根节点rootx相差的列数，圆环形需要取模300。

x和y进行合并时：

- F[rooty] = rootx
- sum[rooty] = (300 + sum[x] - sum[y]) % 300

x进行更新时：

- sum[x] = (sum[x] + sum[rootx) % 300

判断操作：

- (300 + sum[y] - sum[x]) % 300 != val

具体参见代码，这一系列的题目其实都是一样的。

### 代码

Status | Accepted |
---|---|

Time | 280ms |

Memory | 2072kB |

Length | 988 |

```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50010;
int F[maxn];
int sum[maxn];
int find(int x)
{
if (x == F[x])
return x;
int tmp = find(F[x]);
sum[x] = (sum[x] + sum[F[x]]) % 300;
F[x] = tmp;
return F[x];
}
int main()
{
int n, m, x, y, val, ans;
while (scanf("%d%d", &n, &m) == 2)
{
ans = 0;
for (int i = 0; i <= n; ++i)
{
F[i] = i;
sum[i] = 0;
}
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &x, &y, &val);
int rootx = find(x), rooty = find(y);
if (rootx != rooty)
{
F[rooty] = rootx;
sum[rooty] = (300 + sum[x] - sum[y] + val) % 300;
}
else
{
if ((300 + sum[y] - sum[x]) % 300 != val)
ans++;
}
}
printf("%d\n", ans);
}
return 0;
}
```

The end.

2018-04-20 星期五