最小生成树板子

kruskal算法
并查集

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct node{
   
	int a,b,c;
}edge[5000];
int fa[100010],ans;
bool cmp(node a,node b){
   
	return a.c<b.c;
}
int get(int x){
   
	if(x==fa[x])	return x;
	return fa[x]=get (fa[x]);
}
void Union(int x,int y,int i){
   
	int newx=get(x);
	int newy=get(y);
	if(newx==newy)	return;
	fa[newx]=newy;
	ans+=edge[i].c;
}
int main(){
   
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF&&n){
   
		ans=0;
		for(int i=1;i<=n;i++)
			scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
		sort(edge+1,edge+1+n,cmp);
		for(int i=1;i<=m;i++)	fa[i]=i;
		for(int i=1;i<=n;i++)	Union(edge[i].a,edge[i].b,i);
		int flag=1;
		int t=get(1);
		printf("%d\n",ans);                                                                              
	}
	return 0;
}

prim算法
类似于dijkstra
hdu 1863

#include<stdio.h>
#include<string.h>
#define inf 99999999
int map[110][110],dis[110],book[110];
int m,n;
int prim(){
   
	int i,j,count=0,sum=0,k,min=0;
	for(i=1;i<=m;i++)
		dis[i]=map[1][i];
	dis[1]=0;
	book[1]=1;
	count++;
	while(count<m){
   
		min=inf;
		for(i=1;i<=m;i++){
   
			if(book[i]==0&&dis[i]<min){
   
				min=dis[i];
				j=i;
			}
		}
		if(min==inf)
			return 0;
		book[j]=1;
		count++;
		sum+=dis[j];
		for(k=1;k<=m;k++){
   
			if(book[k]==0&&dis[k]>map[j][k])
				dis[k]=map[j][k];
		}
	}
	return sum;
}
int main(){
   
	int i,j,k,a,b,c,sum;
	while(scanf("%d%d",&n,&m)!=EOF&&n){
   
		sum=0;
		memset(book,0,sizeof(book));
		for(i=1;i<=m;i++)
			for(j=1;j<=m;j++){
   
				if(i==j)
					map[i][j]=0;
				else
					map[i][j]=inf;
			}
		for(i=1;i<=m;i++)
			dis[i]=inf;
		for(i=1;i<=n;i++){
   
			scanf("%d%d%d",&a,&b,&c);
			if(c<map[a][b])
				map[a][b]=map[b][a]=c;
		}	
		sum=prim();
		if(sum)
			printf("%d\n",sum);	
		else
			printf("?\n");
	}
	return 0;
 }