洛谷——修复公路[亲测有效]

洛谷——修复公路[亲测有效]按照时间排序,逐个unite。#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintmaxn=1010;structedge{intx,y,t;}a[100010];intn,m,fa[maxn],c…

按照时间排序,

逐个unite。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct edge{
   
   int x,y,t;}a[100010];
int n,m,fa[maxn],cnt;
void init(){
    for(int i=1;i<=n;i++)fa[i]=i;
}
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    cnt--;fa[x]=y;
}
bool cmp(edge x,edge y){
    return x.t<y.t;
}
int main()
{
    scanf("%d%d",&n,&m);init();cnt=n;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        unite(a[i].x,a[i].y);
        if(cnt==1){printf("%d",a[i].t);break;}
    }
    if(cnt>1)puts("-1");
    return 0;
}

本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。

转载于:https://www.cnblogs.com/Yzyet/p/7257567.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/10591.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注