HDOJ1301“Jungle Roads”

秒速五厘米 2022-05-19 04:18 132阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> <h1>原题链接：<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1301" rel="nofollow">http://acm.hdu.edu.cn/showproblem.php?pid=1301</a></h1> <img alt="" height="244" src="https://img-blog.csdn.net/20180720104219484?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjQxOTM0/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" width="370">Problem Description &nbsp; 给你几个点，给出点与点之间的距离，求最小生成树。 &nbsp; Sample Input 9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0 &nbsp; Sample Output 216 30 </td> 
 </tr> 
 </tbody> 
</table>

这是一道最小生成树·算法题，最小生成树有两种方法：一是prim算法 [https://mp.csdn.net/postedit/81133651][https_mp.csdn.net_postedit_81133651]，二是Kruskal算法。

也可以做做大量图论题：[https://mp.csdn.net/postedit/81161939][https_mp.csdn.net_postedit_81161939]

#include<iostream>
 #include<stdio.h>
 using namespace std;
 #define MAX 100
 #define MAXCOST 0x7fffffff
 int graph[MAX][MAX];
 int prim(int graph[][MAX], int n)
 {
 	int lowcost[MAX];//i-max的距离 	
 	int mst[MAX];//表示i的起点是谁 	
 	int i, j, min, minid, sum = 0;
 	for (i = 2; i <= n; i++)	
 	{	
 		lowcost[i] = graph[1][i];	
 		mst[i] = 1;
 	}//默认起点是1 	
 	mst[1] = 0;
 	for (i = 2; i <= n; i++)	
 	{
 	min = MAXCOST;	
 	minid = 0;	
 		for (j = 2; j <= n; j++)	
 		{	
 				if (lowcost[j] < min && lowcost[j] != 0)		
 				{		
 				min = lowcost[j];	
 				minid = j;
 				}
 		}//找出距离1最近的点 
 	sum += min;
 	lowcost[minid] = 0;
 		for (j = 2; j <= n; j++)	
 		{
 			if (graph[minid][j] < lowcost[j])	
 			{
 				lowcost[j] = graph[minid][j];	
 				mst[j] = minid;
 			}
 		}//相当于利用mind作为新的起点来更新lowcost[]; 
 	}
 	return sum;
 }
 int main()
 {
 	int i, j, k, m, n,t,l;
 	char s;
 	int x, y, cost;
 	while(~scanf("%d",&m)&&m){//m=顶点的个数，n=边的个
 	//初始化图G
 	for (i = 1; i <= m; i++)
 	{
 		for (j = 1; j <= m; j++)	
 		{
 			graph[i][j] = MAXCOST;
 		}
 	}
 	//构建图G
 	for (k = 1; k <m; k++)	
 	{
 		getchar();
 		scanf("%c %d",&s,&t);
 		l=(s-'A')+1;
 		if(t>0)
 		{
 			for(i=0;i<t;i++)	
 			{
 				getchar();
 				scanf("%c %d",&s,&cost);
 				j=(s-'A')+1;
 				graph[l][j] = cost;
 				graph[j][l] = cost;
 			}
 		}
 	}	
 	cost = prim(graph, m);
 	cout << cost << endl;
 	}
 	return 0;
 }

[https_mp.csdn.net_postedit_81133651]: https://mp.csdn.net/postedit/81133651
[https_mp.csdn.net_postedit_81161939]: https://mp.csdn.net/postedit/81161939