Prim && Kruskal

www.cnblogs.com/shaokele/

---

题目地址：　　luoguP3366 【模板】最小生成树

Prim && Kruskal

Prim

　　复杂度为 (O(n^2)) ，使用堆优化复杂度为 (O(mlogn))

#include <cstdio> 
#include <cstring>
using namespace std;
const int N=5005;
int n,m,inf,ans,mat[N][N],dis[N];
bool vis[N];
int main(){
	scanf("%d%d",&n,&m);
	memset(mat,0x3f,sizeof(mat));
	inf=mat[0][0];
	for(int i=1;i<=n;i++)
		mat[i][i]=0;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(mat[u][v]>w)
			mat[u][v]=mat[v][u]=w;
	}
	for(int i=1;i<=n;i++)
		dis[i]=mat[1][i];
	vis[1]=1;
	for(int i=1;i<n;i++){
		int min=inf,k=-1;
		for(int j=1;j<=n;j++)
			if(!vis[j] && dis[j]<min){
				min=dis[j];
				k=j;
			}
		if(k==-1){
			puts("orz");
			return 0;
		}
		vis[k]=1;
		ans+=dis[k];
		for(int j=1;j<=n;j++)
			if(!vis[j] && dis[j]>mat[k][j])
				dis[j]=mat[k][j];
	}
	printf("%d
",ans);
	return 0;
}

Kruskal

　　复杂度为 (O(mlogm + mα(m)))

#include <cstdio> 
#include <algorithm>
using namespace std;
int n,m,ans,fa[5005];
struct edge{
	int u,v,w;
}e[200005];
int find(int x){
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
bool cmp(edge a,edge b){
	return a.w<b.w;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	int cnt=0;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int fu=find(e[i].u);
		int fv=find(e[i].v);
		if(fu==fv)continue;
		ans+=e[i].w;
		fa[fv]=fu;
		if(++cnt==n-1){
			printf("%d
",ans);
			return 0;
		}
	}
	puts("orz");
	return 0;
}