prim (堆)

#include <bits/stdc++.h>
using namespace std;
int n,m,tot,ans;
bool vis[1000100];
struct op{
	int vlu,to;
	op(int a,int b){vlu=a,to=b;}
	friend bool operator < (const op aa,const op bb){//重载小于号  注意不能重载大于号
		if(aa.vlu != bb.vlu) return aa.vlu < bb.vlu;
	}
};
struct node {
	int to,vlu;
} pll;
vector<node> adj[1000100];
priority_queue <op> stk;
void insert_edge(int u,int v,int w) {
	pll.to = v;
	pll.vlu = w;
	adj[u].push_back(pll);
	pll.to = u;
	adj[v].push_back(pll);
	pll.to = pll.vlu = 0;
}
void put_stk(int x) {
	vis[x] = 1;
	for(int i=0; i<adj[x].size(); ++i) {
		int v = adj[x][i].to,w = adj[x][i].vlu;
		if(!vis[v]) stk.push(op(w,v));
	}
}
int pop_stk() {
	int pop_temp = 0;
	while(vis[stk.top().to] && !stk.empty()) stk.pop();
	if(!stk.empty()){
		pop_temp = stk.top().vlu;
		put_stk(stk.top().to);
		stk.pop();
	}
	return pop_temp;
}
void prim(int x) {
	memset(vis,0,sizeof(vis));
	vis[x] = 1;
	put_stk(x);
	while(!stk.empty()) ans += pop_stk();
}
void dfs(int x) {
	vis[x] = 1;
	for(int i=0; i<adj[x].size(); ++i) {
		int v = adj[x][i].to;
		if(!vis[v]) dfs(v);
	}
	return;
}
bool pd() {
	dfs(1);
	for(int i=1; i<=n; i++) if(!vis[i]) return 0;
	return 1;
}
int main() {
	cin>>n>>m;
	int u,v,w;
	for(int i=1; i<=m; i++) {
		scanf("%d %d %d",&u,&v,&w);
		insert_edge(u,v,w);
	}
	if(m >= n - 1 && pd()) {
		prim(1);
		cout<<ans;
	} else cout<<"orz";
	return 0;
}

kru (AC)

#include <bits/stdc++.h>
using namespace std;
int f[1000100];
int n,m,tot,ans;
bool vis[1000100];
struct edge{
	int pre,to,w; 
}e[1000100];
vector<int> adj[1000100];
bool cmp(edge px,edge py){return px.w < py.w;}
void insert_edge(int u,int v,int w){
	e[++tot].pre = u;
	e[tot].to = v;
	e[tot].w = w;
	adj[u].push_back(v);
	adj[v].push_back(u);
}
int find(int x){
	if(f[x] == x) return x;
	else return f[x] = find(f[x]);
}
void kpp(){
	int fa = 0,fb = 0;
	for(int i=1;i<=tot;i++){
		fa = find(e[i].pre),fb = find(e[i].to);
		if(fa != fb) f[fa] = fb,ans += e[i].w;
	}
}
void dfs(int x){
	vis[x] = 1;
	for(int i=0;i<adj[x].size(); ++i){
		int v = adj[x][i];
		if(!vis[v]) dfs(v);
	}
	return;
}
bool pd(){
	dfs(1); 
	for(int i=1;i<=n;i++) if(!vis[i]) return 0;
	return 1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i] = i;
	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&u,&v,&w);
		insert_edge(u,v,w);
	}	
	if(m >= n - 1 && pd()){
		sort(e+1,e+tot+1,cmp);
		kpp();
		cout<<ans;
	}
	else cout<<"orz";
	return 0;
}