1 #include<bits/stdc++.h> 2 3 using namespace std; 4 int f[100001]; 5 int a[100001]; 6 7 struct node 8 { 9 int x,y,z; 10 }b[100001]; 11 12 int find(int k) 13 { 14 if(f[k]==k) 15 return k; 16 else 17 return f[k]=find(f[k]); 18 } 19 int n,m; 20 int _flag; 21 int tot; 22 int flag[100001]; 23 bool pd(int x) 24 { 25 for(int i=1;i<=n;i++) 26 f[i]=i; 27 for(int i=1;i<=m;i++) 28 { 29 if(b[i].z < x) continue; 30 int p=find(b[i].x),q=find(b[i].y); 31 f[p]=q; 32 } 33 for(int i=1;i<=tot;i++) 34 if(find(a[flag[i]])!=find(flag[i])) 35 return 0; 36 37 return 1; 38 } 39 40 41 bool cmp(node x,node y) 42 { 43 return x.z>y.z; 44 } 45 46 int main() 47 { 48 ios::sync_with_stdio(false); 49 cin>>n>>m; 50 int l=-1,r=0x3f3f3f3f; 51 for(int i=1;i<=n;i++) 52 { 53 cin>>a[i]; 54 if(a[i]!=i) 55 { 56 tot++; 57 _flag=1; 58 flag[tot]=i; 59 } 60 } 61 for(int i=1;i<=m;i++) 62 { 63 cin>>b[i].x>>b[i].y>>b[i].z; 64 } 65 // sort(b+1,b+1+n,cmp); 66 int ans; 67 if(!_flag) 68 { 69 cout<<"-1"; 70 return 0; 71 } 72 while(l<=r) 73 { 74 75 int mid=(l+r)>>1; 76 if(pd(mid)) 77 {l=mid+1; 78 ans=mid; 79 80 } 81 else 82 r=mid-1; 83 } 84 cout<<ans; 85 return 0; 86 }
原文:https://www.cnblogs.com/Hehe-0/p/14727862.html