蠢到爆炸

回复帖子

@垃圾一个de小号 2019-05-24 16:55 回复

20分……

#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b;
    long long v;
}p[100000];
long long fa[100000001];
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y) 
{
    x=find(x);y=find(y);
    if(x==y) return;
    fa[y]=x;
    return;
}
bool cmp(node a,node b)
{
    return a.v<b.v;
}
int main()
{
    int n,m;
    cin>>n>>m;
    int i;
    for(i=1;i<=m;i++)
        cin>>p[i].a>>p[i].b>>p[i].v;
    sort(p+1,p+1+n,cmp);
    for(i=1;i<=n;i++)
        fa[i]=i;
    long long maxn=-0x7ffffff;
    int k=0;
    for(i=1;i<=m;i++){
        if(find(p[i].a)!=find(p[i].b)){
            merge(p[i].a,p[i].b);
            k++;
            maxn=max(maxn,p[i].v);
        }
        if(k==n-1) break;
    }
    cout<<maxn;
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。