查看原帖
482230
zhz_aleph_114514楼主2022/11/20 15:18
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
struct man{
	int x,y,z;
}f[100005];

int n,m;
int a[20005],b[20005];

bool cmp(man a, man b){
    return a.z>b.z;
}

int findfa(int x){
    if(a[x]==x) return x;
    a[x]=findfa(a[x]);
    return a[x];
}

void mg(int x, int y){
    x=findfa(a[x]);
    y=findfa(a[y]);
    a[x]=y;
}

bool inone(int x, int y){
    x=findfa(x);
    y=findfa(y);
    if(x==y) return true;
    return false;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) a[i]=i;
    for(int i=0;i<m;i++) cin>>f[i].x>>f[i].y>>f[i].z;
    sort(f,f+m,cmp);
    for(int i=0;i<=m;i++){
        if(inone(f[i].x,f[i].y)){
			cin>>f[i].z;
			break;
		}
        else{
            if(!b[f[i].x]) b[f[i].x]=f[i].y;
            else mg(b[f[i].x],f[i].y);
            if(!b[f[i].y]) b[f[i].y]=f[i].x;
            else mg(b[f[i].y],f[i].x);
        }
    }
    return 0;
}
2022/11/20 15:18
加载中...