//2123124  	2010-03-23 17:04:21  	  Accepted  	2966  	C++  	10  	1172  	Xredman
#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;

const int MAX_SIZE = 502;
const int INF = 0x7FFFFFFF;

int G[MAX_SIZE][MAX_SIZE];
int lowcost[MAX_SIZE];

int n;//共有n个节点
int m;

void readin()
{
	int i, j;
	int a, b, cost;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{	
			G[i][j] = INF;
			if(i == j)
				G[i][j] = 0;
		}
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &cost);
		G[a][b] = G[b][a] = cost;
	}
}

int prim(int v0)
{
	int i, j, k, minx;
	int sum = 0;
	for(i = 0; i < n; i++)
	{//初始化辅助数组
		lowcost[i] = G[v0][i];
	}
	lowcost[v0] = -1;
	for(i = 1; i < n; i++)
	{
		//寻找离生成树最近的未加入顶点k
		minx = INF;
		for(j = 0; j < n; j++)
		{
			if(lowcost[j] < minx && lowcost[j] >= 0)
			{
				minx = lowcost[j];
				k = j;
			}
		}

		//将顶点k加入生成树
		lowcost[k] = -1;

		sum += minx;
		//cout<<minx<<endl;
		/*
		*生成树中增加一条新边k到closeset[k],
		*修正各点的lowcost和closeset值
		*/
		for(j = 0; j < n; j++)
		{
			if(G[k][j] < lowcost[j])
			{
				lowcost[j] = G[k][j];
			}
		}
	}
	return sum;
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T-- && scanf("%d%d", &n, &m))
	{
		readin();
		printf("%d\n", prim(0));
	}
	return 0;
}

• 相关文章
• 全局相关文章