MST之prim求解。

//6612475 Xredman 2485 Time Limit Exceeded   C++ 1131B 2010-03-23 08:21:16 
//超时源于写错了T 
//6612480 Xredman 2485 Accepted 560K 157MS C++ 1227B 2010-03-23 08:24:18 
//problem:http://acm.pku.edu.cn/JudgeOnline/problem?id=2485
#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],closeset[MAX_SIZE];

int n;//共有n个节点

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

int prim(int v0)
{
	int i, j, k, minx;
	int res = -1;
	int sum = 0; 
	for(i = 0; i < n; i++)
	{//初始化辅助数组
		lowcost[i] = G[v0][i];
		closeset[i] = v0;
	}
	
	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] = 0;
		if(minx > res)
			res = minx;
		sum += minx;
		/*
		*生成树中增加一条新边k到closeset[k],
		*修正各点的lowcost和closeset值
		*/
		for(j = 0; j < n; j++)
		{
			if(G[k][j] < lowcost[j])
			{
				lowcost[j] = G[k][j];
				closeset[j] = k;
			}
		}
	}
	cout<<sum<<endl;
	return res;
}

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

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