最小生成树问题 普利姆算法简单模板 hdoj1233

#include <iostream>
#include <cstring>
#include <cstdio>
#define  N   105
using namespace std;
int n,m,a[N][N],b[N];;
const int inf=0x3f3f3f3f;
int prim()
{
	int i,j,t,k,s,f[N],r=0;
	memset(f,0,sizeof(f));
	for(t=i=f[1]=1 ; i<n ; i++)
	{
		for(s=inf,j=1 ; j<=n ; j++)
		{	
			if(a[t][j]<b[j] && !f[j]) b[j]=a[t][j];
			if(s>b[j] && !f[j]) k=j,s=b[j];
		}
		f[k]=1,r+=s,t=k;
	}
	return r;
}
int main ()
{
	//freopen("z.txt","r",stdin);
	while(scanf("%d",&n),n)
	{
		m=n*(n-1)>>1;
		int x,y,z;
		memset(b,0x3f3f3f3f,sizeof(b));
		memset(a,0x3f3f3f3f,sizeof(a));
		for(int i=0 ; i<m ; i++)
			scanf("%d%d%d",&x,&y,&z),
			a[x][y]=a[y][x]=z;
		printf("%d\n",prim());
	}
	return 0;
}

最小生成树，可能是图论里面最最简单的一个小算法了。几天前学了这个算法，简单的模拟了整个算法过程！权当以后的模板用了！