一个体育场列标号为1-300,行无限(一列可以有多人重复坐体育场是一个环。给出n个人和m个关系,关系为A B x表示A位置若为i,则B位置在A顺时针加x的位置。如果一个关系在前面给出的关系中矛盾,则称其不成立。求不正确的关系个数Input输入多组数据,第一行n,m(1N50,000,0M100,000)表示人数和关系数接下来m行表示关系 A(1AN), B(1BN), X(0X300) (A!B)Output对于每组数据输出不正确的关系个数。Sample Input10 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 Output2Hint: PS the 5th and 10th requests are incorrect如果一个后面给出的关系与前面给出的关系矛盾则后面的关系是错误的。在输入一组关系后首先判断这组信息中的A和B是否已经存在关系。如果没有关系则把前面的点变成后一点的祖先并建立距离关系带权并查集如果有关系则判断前后关系是否矛盾。注意find函数中查找某一点祖先时需将某一点到祖先路径上的所有点到祖先的距离都要修改。还有这个式子dis[dy]dis[x]d-dis[y]其中dy和dx分别为y和x的祖先通过合并dx要变成dy的祖先见下图关系。#includecstdio using namespace std; const int mod300; int pre[50005],dis[50005]; int find1(int x) //递归回溯找祖先并压缩路径计算路径上所有点到祖先的距离 { if(pre[x]!x) { int jpre[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 ans0; for(int i1; in; i) //初始化 { dis[i]0; pre[i]i; } for(int i0; im; i) { int x,y,d; scanf(%d%d%d,x,y,d); int dxfind1(x),dyfind1(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; }