2 条题解

  • 1
    @ 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;
    }
    
    • 0
      @ 2022-10-23 14:58:45
      /*****************************************
      Note:
      ******************************************/
      #include <queue>
      #include <set>
      #include <math.h>
      #include <stack>
      #include <stdio.h>
      #include <iostream>
      #include <vector>
      #include <iomanip>
      #include <string.h>
      #include <algorithm>
      #include <cstdio>
      #include <cstring>
      using namespace std;
      #define LL long long
      const int N = 1e5 + 10;
      const int INF = 0x3f3f3f3f;
      int n,m,fa[N];
      struct node{
      	int a,b,dis;
      }p[N];
      void init()
      {
      	for(int i=1;i<=n;i++)
      		fa[i]=i;
      }
      int find(int x)
      {
      	return (fa[x]==x)?x:fa[x]=find(fa[x]);
      }
      bool cmp(node a,node b)
      {
      	return a.dis<b.dis;
      }
      void kruskal()
      {
      	int sum=-INF,cnt=0;
      	for(int i=1;i<=m;i++)
      	{
      		if(cnt==n-1) break;
      		int x=find(p[i].a),y=find(p[i].b);
      		if(x!=y)
      		{
      			cnt++;
      			sum=max(sum,p[i].dis);
      			fa[x]=y;
      		}
      	}
      	cout<<cnt<<" "<<sum<<endl;
      }
      int main()
      {
      	cin>>n>>m;
      	init();
      	for(int i=1,u,v,c;i<=m;i++)
      	{
      		cin>>u>>v>>c;
      		p[i].a=u,p[i].b=v,p[i].dis=c;
      	}
      	sort(p+1,p+m+1,cmp);
      	kruskal();
      	return 0;
      }
      
      • 1

      信息

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