1301 jungle roads.cpp

来自「威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。」· C++ 代码 · 共 60 行

//最小生成树
#include <iostream>
using namespace std;
const int Max=0x7fffffff;
int map[30][30],n;
int value[30];

int mintree_prim()
{
	int i,j,k,len=0,minp,mind;
	
	for(i=0;i<30;i++)
		if(map[0][i]!=0)
			value[i]=map[0][i];
		else
			value[i]=Max;
	for(i=0;i<30;i++)
		map[i][0]=0;
	for(i=1;i<n;i++)
	{
		mind=Max;
		for(j=0;j<30;j++)
			if(value[j]<mind)
			{
				mind=value[j];
				minp=j;
			}
		value[minp]=Max;
		len+=mind;
		for(j=0;j<30;j++)
			map[j][minp]=0;
		for(j=0;j<30;j++)
			if(map[minp][j]!=0 && map[minp][j] < value[j] )
				value[j]=map[minp][j];
	}
	return len;
}

int main()
{
	int t,c,i;
	char s,e;
	
	while( cin>>n && n)
	{
		for(i=0;i<n-1;i++)
		{
			cin>>s>>t;
			while(t--)
			{
				cin>>e>>c;
				map[s-'A'][e-'A']=c;
				map[e-'A'][s-'A']=c;
			}
		}
		cout<< mintree_prim() <<endl;
	}
	return 0;
}