Description
　　觀眾席每一行構(gòu)成一個圓形，每個圓形由300個座位組成，對300個座位按照順時針編號1到300,且可以認為有無數(shù)多行?，F(xiàn)在比賽的組織者希望觀眾進入場地的順序可以更加的有趣，在門票上并沒有規(guī)定每個人的座位，而是與這個圈中某個人的相對位置，可以坐在任意一行。
　　門票上標示的形式如下：A B x 表示第B個人必須在A的順時針方向x個位置（比如A坐在4號位子，x=2，則B必須坐在6號位子）。
　　現(xiàn)在你就座位志愿者在入場口檢票。如果拿到一張門票，與之前給定的矛盾，則被視為是假票，如果無矛盾，視為真票?，F(xiàn)在給定該行入場觀眾的順序，以及他們手中的門票，請問其中有多少假票？

Input
　　第一行兩個數(shù)n(1<=n<=50,000)和m(1<=m<=100,000)。n表示人數(shù)。
　　接下來m行，每行三個數(shù)A，B，x標示B必須坐在A的順時針方向x個位置。(1<=A<=N), B(1<=B<=N), X(0<=X<300) (A!=B)
　　以上字母含義如題所述。

Output
　　僅一個數(shù)，表示在m張票中有多少假票。

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

Data Constraint

Hint
【樣例解釋】
　　第5張和第10張是假票
【數(shù)據(jù)范圍】
　　對于20%的數(shù)據(jù)：n<=100
　　對于100%的數(shù)據(jù)：n<=50,000。
.
.
.
.
.

分析

.
.
.
.

程序：

#include<iostream> using namespace std; int n,m,f[50001],d[50001],root1,root2,ans=0,a,b,x; int find(int w) {if (f[w]==w) return w;int t=f[w];f[w]=find(f[w]);d[w]=(d[w]+d[t])%300;return f[w]; }int main() {cin>>n>>m;for (int i=1;i<=n;i++){f[i]=i;d[i]=0;}for (int i=1;i<=m;i++){cin>>a>>b>>x;root1=find(a);root2=find(b);if (root1!=root2){f[root2]=root1;d[root2]=(-d[b]+x+d[a]+300)%300;} elseif ((d[b]-d[a]+300)%300!=x%300) ans++;}cout<<ans;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499935.html

總結(jié)

以上是生活随笔為你收集整理的体育场[带权并查集]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。