1 条题解

  • 0
    @ 2026-9-1 21:11:27
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define N 310
    int n,m;
    struct node{
    	int x,y,w;
    }e[10010];
    bool operator<(node n1,node n2){
    	return n1.w<n2.w;
    }
    
    int fa[N];
    int findfa(int x){
    	return x==fa[x]?x:fa[x]=findfa(fa[x]);
    }
    
    signed main(){
    	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		int x,y,w;cin>>x>>y>>w;
    		e[i]={x,y,w};
    	}
    	
    	sort(e+1,e+m+1);
    	
    	int ans=0;
    	for(int i=1;i<=n;i++)fa[i]=i;
    	for(int i=1;i<=m;i++){
    		int x=e[i].x,y=e[i].y,w=e[i].w;
    		x=findfa(x),y=findfa(y);
    		if(x!=y){
    			fa[x]=y;
    			ans=w;
    		}
    	}
    	
    	cout<<n-1<<' '<<ans<<'\n';
    	
    	return 0;
    }
    
    • 1

    信息

    ID
    2736
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    22
    已通过
    19
    上传者