C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 1232K, 提交时间: 2020-06-20 16:02:59

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node{
	int x,y,len;
}que[200000];

bool bml(Node a,Node b){
	return a.len < b.len;
}
int par[200000];
int find(int x){
	if(par[x] == -1) return x;
	return par[x] = find(par[x]);
}
int main(){
	memset(par,-1,sizeof(par));
	
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>que[i].x>>que[i].y>>que[i].len;
	}
	sort(que,que+m,bml);
	int ans = 0;
	for(int i=0;i<m;i++){
		int a = find(que[i].x);
		int b = find(que[i].y);
		if(a != b){
			par[a] = b;
			ans = max(que[i].len,ans);
		}
	}
	cout<<n-1<<" "<<ans<<endl;
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 156ms, 内存消耗: 24272K, 提交时间: 2020-06-20 13:41:03

def solve():
    n, m = map(int, input().split())
    f = [i for i in range(n + 1)]
    def getF(u):
        if f[f[u]] == f[u]:
            return f[u]
        f[u] = getF(f[u])
        return f[u]
    e = [tuple(map(int, input().split())) for _ in range(m)]
    e.sort(key=lambda x: x[2])
    ansa, ansb = 0, 0
    for u, v, w in e:
        u = getF(u)
        v = getF(v)
        if u != v:
            ansa += 1
            ansb = w
            f[u] = v
    print(ansa, ansb)

while True:
    try:
        solve()
    except EOFError:
        exit(0)

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 524K, 提交时间: 2020-07-19 16:58:58

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int f[100003];
struct road{
	int u,v,w;
}r[10003];
bool jud(road a,road b)
{
	return a.w<b.w;
}
int fa(int x)
{
	if(x==f[x]) return x;
	f[x]=fa(f[x]);
	return f[x];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=1;i<=m;i++)
	cin>>r[i].u>>r[i].v>>r[i].w;
	sort(r+1,r+m+1,jud);
	for(int i=1;i<=m;i++)
	{
		int fu=fa(r[i].u),fv=fa(r[i].v);
		if(fu==fv) continue;
		ans=r[i].w;
		f[fu]=fv;
	}
	cout<<n-1<<' '<<ans<<endl;
	return 0;
}