带权并查集+贪心+排序

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 struct data {
   int x,y,z;}; 5 data f[100005]; 6 int n,m,a[20005],b[20005],i; 7 inline bool cmp(data a,data b) 8 { 9     return a.z>b.z;10 }11 inline int find(int x)12 {13     if(a[x]==x) return x;14     a[x]=find(a[x]);15     return a[x];16 }17 inline void ad(int x,int y)18 {19     x=find(a[x]);20     y=find(a[y]);21     a[x]=y;22 }23 inline bool check(int x,int y)24 {25     x=find(x);26     y=find(y);27     if(x==y) return true;28     return false;29 }30 int main()31 {32     scanf("%d%d",&n,&m);33     for(i=1;i<=n;i++) a[i]=i;34     for(i=1;i<=m;i++)35         scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);36     sort(f+1,f+m+1,cmp);37     for(i=1;i<=m+1;i++)38     {39         if(check(f[i].x,f[i].y)) {printf("%d",f[i].z);break;}40         else41         {42             if(!b[f[i].x]) b[f[i].x]=f[i].y;43                 else {ad(b[f[i].x],f[i].y);}44             if(!b[f[i].y]) b[f[i].y]=f[i].x;45                 else {ad(b[f[i].y],f[i].x);}46         }47     }48     return 0;49 }