求助 P1525只有10分 不知道哪里出错了
  • 板块学术版
  • 楼主hnoi
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/11/6 17:28
  • 上次更新2023/10/27 04:02:02
查看原帖
求助 P1525只有10分 不知道哪里出错了
601142
hnoi楼主2022/11/6 17:28
#include<bits/stdc++.h>
using namespace std;
struct pri{
    int x;
    int y;
    int dis;
}a[200050];
bool cmp(pri a,pri b){
    return a.dis>b.dis;
}
int fa[20005],b[20005];
int get(int x){
    if(fa[x]==x) return x;
    fa[x]=get(fa[x]);
    return fa[x];
}
void hb(int p,int q){
    int x=get(p);
    int y=get(q);
    fa[y]=x;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].dis);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int aa=get(a[i].x);
        int bb=get(a[i].y);
        if(aa==bb){
            cout<<a[i].dis<<endl;
            return 0;
        }
        if(!b[a[i].x]) b[a[i].x]=a[i].y;
        else hb(b[a[i].x],a[i].y);
        if(!b[a[i].y]) b[a[i].y]=a[i].x;
        else hb(b[a[i].y],a[i].x);
    }
    cout<<0<<endl;
    return 0;
}
2022/11/6 17:28
加载中...