讨论 / 给新人们的AC代码
ljw666 2019-04-06 20:13:02
点我顶贴 收藏 删除
#include <bits/stdc++.h>

using namespace std;

const int maxn=20001,maxm=100001;

int n,m,a1,b1,pre[maxn],vis[maxn];

long long ans;

struct node

{

int a,b,val;

}p[maxm<<1];

bool cmp(node x,node y)

{return x.val>y.val;}//注意此处是大的在前面

int find(int x)

{

if(x!=pre[x])pre[x]=find(pre[x]);

return pre[x];

}

void join(int a,int b)

{

int a1=find(a),b1=find(b);

if(a1!=b1)pre[a1]=b1;

}

int main()

{

ios::sync_with_stdio(false);

cin>>n>>m;

for(int i=1;i<=n;i++)

{pre[i]=i;vis[i]=0;}

for(int i=1;i<=m;i++)

cin>>p[i].a>>p[i].b>>p[i].val;

sort(p+1,p+m+1,cmp);

ans=0;

for(int i=1;i<=m;i++)

{

a1=find(p[i].a),b1=find(p[i].b);

if(a1==b1){ans=p[i].val;break;}

if(vis[a1]==0)vis[a1]=b1;//先找一个代表 a1

else join(b1,vis[a1]);//之后把其他人b1 与代表合并

if(vis[b1]==0)vis[b1]=a1;

else join(a1,vis[b1]);

}

printf("%lld\n",ans);

return 0;

}

查看更多回复
提交回复