#include <iostream>
using namespace std;

// 找出最小权集合中的最小权
int findMinEdge(int minCost[], int n)
{
	int i;
	int minIndex = 0;
	while (minCost[minIndex] == 0)
	{
		minIndex++;
	}
	for (i=minIndex+1; i<=n-1; i++)
	{
		if (minCost[i] < minCost[minIndex] && minCost[i] != 0)
		{
			minIndex = i;
		}
	}
	return minIndex;
}

int main()
{
	const bool VISIT = true;
	const bool UNVISIT = false;
	const int N = 27;
        int n;
	int i,j;
	int edges,cost;
	char a,b;
	int minCost[N] = {0}; // 当前MST到各未访问顶点的最小权
	int matrix[N][N] = {0};
	bool flag[N]; // 用来标记顶点是否被访问过
	
	int minSum ; 
	int minIndex;
	
	while (cin>>n && n!=0)
	{
		minSum = 0; 
		for (i=0; i<=n-1-1; i++)
		{
			cin>>a>>edges;
			for (j=0; j<=edges-1; j++)
			{
				cin>>b>>cost;
				matrix[a-'A'][b-'A'] = cost;
				matrix[b-'A'][a-'A'] = cost;			
			}
		}
		
		for (i=0; i<=n-1; i++)  // 第一次访问第一个顶点
		{
			minCost[i] = matrix[0][i];
			flag[i] = UNVISIT;
		}
		flag[0] = VISIT; 
		
		for (i=0; i<=n-1-1; i++)
		{
			minIndex = findMinEdge(minCost, n); // 访问权最小的顶点
			minSum += minCost[minIndex];
			minCost[minIndex] = 0;
			flag[minIndex] = VISIT;// 标志已经访问过
			
			for (j=0; j<=n-1; j++)  // 访问后,再一次处理minCost,求得当前MST到所有未访问的顶点最小权
			{
				if (matrix[minIndex][j] !=0)
				{
					if (matrix[minIndex][j]<minCost[j])
					{
						minCost[j] = matrix[minIndex][j];
					}
					else if (matrix[minIndex][j]>minCost[j] && flag[j]==UNVISIT && minCost[j]==0)
					{
						minCost[j] = matrix[minIndex][j];
					}
				}

				
			}
		}
		cout<<minSum<<endl;
		
	}
	
    return 0;
}

• Re:一个Prim算法引来的血案,大牛帮我一下,为什么测试数据都对了,可是总是WA (50) xujiaming 2009-01-07 16:02:28
  • Re:一个Prim算法引来的血案,大牛帮我一下,为什么测试数据都对了,可是总是WA (108) gfedcba 2009-01-07 17:04:48
  • 一个cin引发的血案,究竟是怎么样的回事,说来听听 (0) gfedcba 2009-01-07 17:06:30
    • Re:一个cin引发的血案,究竟是怎么样的回事,说来听听 (23) xujiaming 2009-01-07 18:21:07