题目：

Zjnu Stadium

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3280    Accepted Submission(s): 1267 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   |   We have carefully selected several similar problems for you:   3172  3038  2473  3045  3046    Statistic |  Submit |  Discuss |  Note 思路：

给出一个n,m,n表示的是有n 个人，m表示的是 有m 对关系： 接下来输入的就是这m对关系，a,b,x；表示的是a，b相距x个距离；然后判断输入的是否与这个数的上面的数信息一致， 输出不一致的数目,出现错误的可能性有一种，就是两个人到根节点的距离相同，这样就出现矛盾了，所以用dis[]数组来记录当前点到根节点的距离，然后dis[fy]=dis[x]+s-dis[y],这一句代码的推导类似于向量，如下图：

根据向量的减法，就可以推出这个公式

代码：

#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <string> #include <iostream> #include <stack> #include <queue> #include <vector> #include <algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #define N 50000+20 #define M 200010 #define MOD 1000000000+7 #define inf 0x3f3f3f3f using namespace std; int pre[N], dis[N],cnt;//dis表示这个节点到根节点的距离 void init(int n) { for(int i=1; i<=n; i++) { pre[i]=i; dis[i]=0; } } int find(int x) { if(pre[x]==x) return x; int temp=pre[x];//找到x的父亲节点 pre[x]=find(pre[x]);//找到x的根节点 dis[x]+=dis[temp];//更新x到根节点的距离 return pre[x]; } void mix(int x,int y,int s) { int fx=find(x); int fy=find(y); if(fx!=fy) { pre[fy]=fx; dis[fy]=dis[x]+s-dis[y];//类似于向量 } else { if(dis[y]-dis[x]!=s)//如果y到根节点的距离减去x到根节点的距离不是s，那么就证明这一句错误 cnt++; } } int main() { int n,m,a,b,c; while(~scanf("%d%d",&n,&m)) { cnt=0; init(n); for(int i=1; i<=m; i++) { scanf("%d%d%d",&a,&b,&c); mix(a,b,c); } printf("%d\n",cnt); } return 0; } PS：借一下这道题来理解理解带权并查集