2 条题解

  • 0
    @ 2022-10-23 15:17:50
    #include<iostream>
    #include<fstream>
    #include<iomanip>
    #include<stdio.h>
    #include<cstdio>
    #include<math.h>
    #include<cmath>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<string.h>
    #include<vector>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    #include<cstdlib>
    #include<stdlib.h>
    #include<ctime>
    #include<time.h>
    using namespace std;
    #define LL long long
    const int N=1e5+5;
    const int INF=0x3f3f3f3f;
    int n,m;
    int fa[11000];
    struct node{
    	int x,y;
    	int z;
    }p[6001000];
    int find(int x){
    	if(x==fa[x]){
    		return x;
    	}
    	return fa[x]=find(fa[x]);
    }
    bool cmp(node a,node b){
    	return a.z<b.z;
    }
    void init(){
    	for(int i=1;i<=n;i++){
    		fa[i]=i;
    	}
    }
    void kruskal(){
    	int sum=0,ans=0;
    	int xx,yy;
    	for(int i=1;i<=m;i++){
    		xx=find(p[i].x);
    		yy=find(p[i].y);
    		if(xx==yy){
    			continue;
    		}
    		fa[xx]=yy;
    		sum=max(sum,p[i].z);
    		ans++;
    	}
    	cout<<ans<<" "<<sum<<endl;
    }
    int main(){
    	/*
    	freopen(".in","r",stdin);
    	freopen(".out","w",stdout);
    	*/
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		cin>>p[i].x>>p[i].y>>p[i].z;
    	}
    	init();
    	sort(p+1,p+1+m,cmp);
    	kruskal();
    	return 0;
    }
    

    信息

    ID
    1325
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    40
    已通过
    21
    上传者