首页 > 代码库 > hdu1301&poj1251 Jungle Roads(最小生成树之prim果题)

hdu1301&poj1251 Jungle Roads(最小生成树之prim果题)


转载请注明出处:http://blog.csdn.net/u012860063

题目链接:

HDU:http://acm.hdu.edu.cn/showproblem.php?pid=1301

POJ: http://poj.org/problem?id=1251


一道prim算法的果题!


题目很长,这里就不贴题目了。

题意: 给你每个村庄之间的维护道路的费用,求最小的费用。

代码如下:


#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 0xfffffff
#define N 147
int map[N][N];
int dis[N],vis[N];
//创建map二维数组储存图表,dis数组记录每2个点间最小权值.
//vis[N]数组标记某点是否已访问 
int min(int a, int b)
{
	return a<b?a:b;
}

int prim(int n, int sta)
{
	int i, j, k, MIN, sum = 0;
	for(i = 1; i <= n; i++)//第一次给dis数组赋值 
	{
		dis[i]=map[sta][i];
		vis[i] = 0;
	}
	vis[sta] = 1;//从某点开始,分别标记和记录该点
	for(i = 1; i < n; i++)//再运行n-1次  
	{
		MIN = INF; k = 0;
		for(j = 1; j <= n; j++)
		{
			if(vis[j]==0 && dis[j]<MIN)//找出最小权值并记录位置
			{
				k = j;
				MIN = dis[j];
			}
		}
		if(k != 0)
		{
			vis[k] = 1; //标记该点
			sum+=dis[k];//最小权值累加 
			for(j = 1; j <= n; j++)//更新权值
			{
				dis[j] = min(map[k][j],dis[j]);
			}
		}
	}
	return sum;
}

int main()
{
	int n, i, j, k, m,t;
	char ch,tt;
	int sum;
	while(cin >> n && n)
	{
		for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                map[i][j]=INF;
			for(i = 1; i < n; i++)
			{
				cin>>ch>>m;
				for(j = 1; j <= m; j++)
				{
					cin>>tt>>t;
					//防止有重边出现
					map[ch-'A'+1][tt-'A'+1]=min(map[ch-'A'+1][tt-'A'+1],t);
					map[tt-'A'+1][ch-'A'+1]=map[ch-'A'+1][tt-'A'+1];
				}
			}
			sum = prim(n,1);
			cout<<sum<<endl;
	}
	return 0;
}