一个体育场列标号为1-300,行无限(一列可以有多人重复坐）体育场是一个环。
给出n个人和m个关系,关系为A B x表示A位置若为i,则B位置在A顺时针加x的位置。如果一个关系在前面给出的关系中矛盾,则称其不成立。求不正确的关系个数
Input
输入多组数据,第一行n,m(1<=N<=50,000,0<=M<=100,000)表示人数和关系数
接下来m行表示关系 A(1<=A<=N), B(1<=B<=N), X(0<=X<300) (A!=B)
Output
对于每组数据，输出不正确的关系个数。
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 100Sample Output
2Hint: （PS： the 5th and 10th requests are incorrect）
如果一个后面给出的关系与前面给出的关系矛盾，则后面的关系是错误的。
在输入一组关系后，首先判断这组信息中的A和B是否已经存在关系。
如果没有关系，则把前面的点变成后一点的祖先，并建立距离关系（带权并查集）
如果有关系，则判断前后关系是否矛盾。
注意find函数中查找某一点祖先时，需将某一点到祖先路径上的所有点到祖先的距离都要修改。
还有这个式子dis[dy]=dis[x]+d-dis[y]，其中dy和dx分别为y和x的祖先，通过合并dx要变成dy的祖先（见下图关系）。
#include<cstdio> using namespace std; const int mod=300; int pre[50005],dis[50005]; int find1(int x) //递归回溯找祖先，并压缩路径，计算路径上所有点到祖先的距离 { if(pre[x]!=x) { int j=pre[x]; pre[x]=find1(j); dis[x]=(dis[x]+dis[j])%mod; //防止到祖先的距离超过一圈 } return pre[x]; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int ans=0; for(int i=1; i<=n; i++) //初始化 { dis[i]=0; pre[i]=i; } for(int i=0; i<m; i++) { int x,y,d; scanf("%d%d%d",&x,&y,&d); int dx=find1(x),dy=find1(y); //找到祖先，计算路径上所有点到祖先的距离 if(dx!=dy) //(union)若不是并联，则把前面的点变成后一点的祖先 { pre[dy]=dx; dis[dy]=(dis[x]+d-dis[y]+mod)%mod; //防止出现负数加上300再取模 } else if(dis[y]!=(dis[x]+d)%mod) //防止到祖先的距离超过一圈 ans++; } printf("%d\n",ans); } return 0; }
