R201221037 记录详情

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge{
	int w,to,next;
}edge[10000001];
int uf[10000001]={0},n,k;
int find(int n){
	if(uf[n]==n)return n;
	uf[n]=find(uf[n]);
	return uf[n];
}
bool cmp(Edge a,Edge b){
	return a.w<b.w;
}
int kruskal(){
	int ans=0,num=0; 
	for(int i=1;i<=n;i++){
		if(find(edge[i].to)==find(edge[i].next))continue;
		ans+=edge[i].w;
		uf[edge[i].next]=find(edge[i].to);
		num++;
		if(num==k-1)return ans;
	}
	return -1;
}
int main() {
	memset(uf,1,sizeof(uf));
    cin>>k>>n;
    for(int i=1;i<=n;i++){
    	int a,b,c;
    	cin>>a>>b>>c;
		edge[i]={c,a,b};
	}
	sort(edge+1,edge+1+n,cmp);
	for(int i=1;i<=k;i++)uf[i]=i;
	int qwq=kruskal();
	if(qwq==-1){
		cout<<"orz"<<endl;
		return 0;
	}
	else{
		cout<<qwq<<endl;
	}
    return 0;
}