Kruskal版题解

一般来说，求最小生成树的算法有两种：Kruskal算法和Prim算法。本题用的是Kruskal，Prim我其实也试过，结果翻车了（翻车代码我会放在最后），“荣获”了5个测试点AC，2个WA，3个TLE。

---

Kruskal运用了贪心的思想，其核心思想为：先选1条权值最小的边并连接，再选权值次小的（当然前提是不能构成环）……直到所有点连通为止。作为生成树，应当在$cnt=N-1$时成立（想必都能做到这题了，树是什么还是已经了解了吧）。一般此算法的时间复杂度为$O(M^2)$，在这题中会出现超时，但通过并查集压缩后，找根节点的时间复杂度变成了$O(1)$，时间复杂度也就降为$O(M)$，过了！

//尽管用吧，保证能AC（差点就拿到时间刺客了）
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int x,y,z;
}a[200005];
int n,m,cnt=0,ans=0,u,v,w,tr[100005];//cnt用于统计边数，ans为最小权值
bool cmp(node a,node b){//排序，变为升序后才能用贪心
    return a.z<b.z;
}
int find(int x){//并查集
    if(tr[x]==x) return x;
    return tr[x]=find(tr[x]);
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) tr[i]=i;
    for(int i=0;i<m;i++) cin>>a[i].x>>a[i].y>>a[i].z;
    sort(a,a+m,cmp);
    for(int i=0;i<m;i++){
        u=a[i].x,v=a[i].y,w=a[i].z;
        if(find(u)!=find(v)) tr[find(u)]=find(v),cnt++,ans+=w;
    }
    if(cnt==n-1) cout<<ans;
    else cout<<"orz";
    return 0;
}

---

Prim用的思想也是贪心，同时类似于Dijkstra算法（其实我也不太会），大致方法为：让所有点开始时处于未标记的状态，每次更新能到达的点及最短路径，接下来过程的就只能靠你自己了……
下面是我的翻车记录，别抄了，AK不了的，自己看数据代入时间复杂度（也就$O(N^2)$）吧。事先看了其他题解，基本上也都是用Kruskal做的。

//翻车了
#include<iostream>
#include<cstring>
using namespace std;
//凌乱不堪的全局变量，别学我的（尤其是开万能头那些，命名实在太容易冲突了）
//原版是一行涵盖全部变量的，切开了省得还要滚动才能看全
int e[400005],w[400005],ne[400005],h[100005],idx;
int n,m,vis[100005],d[100005],x,y,z,id,ans=0;
void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;//链式前向星也救不了这题的TLE
}
bool prim(){
	memset(d,0x3f,sizeof d);
	d[1]=0;
	for(int i=1;i<=n;i++){//Prim记得从1开始
		id=-1;
		for(int j=1;j<=n;j++){
			if(vis[j]==0&&(id==-1||d[id]>d[j])) id=j;
		}
		if(id==-1) return false;
		vis[id]=1;
		for(int j=h[id];j!=-1;j=ne[j]){
			int yy=e[j],zz=w[j];
			if(vis[yy]==0) d[yy]=min(zz,d[yy]);
		}
	}
	return true;
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    if(n>m+1){
        cout<<"orz";
        return 0;
    }
    while(m--){
    	cin>>x>>y>>z;
    	add(x,y,z);
    	add(y,x,z);
	}
	if(prim()){
		for(int i=1;i<=n;i++) ans+=d[i];
		cout<<ans;
	}
	else cout<<"orz";
    return 0;
}