hdu 1233 還是暢通工程(prim||kruskal)

這個完完全全就是模板題目，沒有一點變化，就是單純的讓求最小生成樹

代碼：（prim）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 0x7fffffff

using namespace std;
int gra[105][105];
int n;
void prim()
{
	int visit[105],d[105],i,j,now,MIN,sum = 0;
	memset(visit,0,sizeof(visit));
	for(i=1; i<=n; i++)
		d[i] = MAX;
	now = 1,visit[1] = 1,d[1] = 0;
	for(i=2; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			if(!visit[j] && d[j]>gra[now][j])
				d[j] = gra[now][j];
		}
		MIN = MAX;
		for(j=1; j<=n; j++)
			if(!visit[j] && d[j]> n,n)
	{
		for(i=1; i<=n*(n-1)/2; i++)
		{
			cin >> a >> b >> c;
			gra[a][b] = gra[b][a] = c;
		}
		prim();
	} 
	return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 10010000

using namespace std;
int n,p[105];
struct node
{
	int i,j,len;
}gra[5500];
int cmp(const void *a,const void *b)
{
	return ((node *)a)->len - ((node *)b)->len;	
}
int find(int x)
{
	return p[x] == x? x:p[x] = find(p[x]);
}
void kruskal()
{
	int i,sum = 0;
	for(i=1; i<=n*(n-1)/2; i++)
	{
		int x = find(gra[i].i);
		int y = find(gra[i].j);
		if(x != y)
		{
			sum += gra[i].len;
			p[x] = y;
		}
	}
	cout << sum << endl;
}
int main()
{
	int i,j;
	while(cin >> n,n)
	{
		for(i=1; i<=n*(n-1)/2; i++)
		{
			cin >> gra[i].i >> gra[i].j >> gra[i].len;
		}
		for(i=1; i<=n; i++)
			p[i] = i;
		qsort(gra+1,n*(n-1)/2,sizeof(gra[0]),cmp);
		kruskal();
	}
	return 0;
}