InputThere 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.
OutputFor 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）
1 #include<stdio.h> 2 #include<map> 3 #include<iostream> 4 #include<string.h> 5 #include<algorithm> 6 #include<stack> 7 #include<cmath> 8 #include<vector> 9 using namespace std; 10 typedef long long ll; 11 const int N=50020; 12 13 int f[N],d[N],n; 14 15 void init() 16 { 17 for(int i=1;i<=n;i++) 18 { 19 f[i]=i; 20 d[i]=0; 21 } 22 } 23 int getf(int x) 24 { 25 if(f[x]==x) 26 return x; 27 else 28 { 29 int t=f[x];//找它的父节点 30 f[x]=getf(f[x]); 31 d[x]=d[x]+d[t];//d[x]（为x到根节点的距离）更新为它到它父节点的距离+父节点到根节点的距离 32 return f[x]; 33 } 34 } 35 36 void merge(int x,int y) 37 { 38 int t1=getf(x); 39 int t2=getf(y); 40 if(t1!=t2) 41 f[t2]=t1; 42 return; 43 } 44 45 int main() 46 { 47 int m,x,y,z; 48 while(~scanf("%d %d",&n,&m)) 49 { 50 init(); 51 int ans=0; 52 for(int i=0;i<m;i++) 53 { 54 scanf("%d %d %d",&x,&y,&z); 55 int fx=getf(x),fy=getf(y); 56 if(fx==fy) 57 { 58 int w=d[y]-d[x]; 59 if(w!=z) 60 ans++; 61 } 62 else 63 { 64 merge(x,y); //f[fy]=x; 65 d[fy]=d[x]+z-d[y]; 66 } 67 } 68 cout<<ans<<endl; 69 } 70 return 0; 71 }
原文：https://www.cnblogs.com/OFSHK/p/11992852.html