图结构练习——最小生成树
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^
题目描述
有n个城市,其中有些城市之间可以修建公路,修建不同的公路费用是不同的。现在我们想知道,最少花多少钱修公路可以将所有的城市连在一起,使在任意一城市出发,可以到达其他任意的城市。
输入
输入包含多组数据,格式如下。 第一行包括两个整数n m,代表城市个数和可以修建的公路个数。(n<=100) 剩下m行每行3个正整数a b c,代表城市a 和城市b之间可以修建一条公路,代价为c。
输出
每组输出占一行,仅输出最小花费。
示例输入
3 2
1 2 1
1 3 1
1 0
示例输出
2
0
prim代码:
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 int map[101][101];
5 int m,n;
6 int prim()
7 {
8 int lowcost[101];
9 int f[101]={0};
10 int g[100];
11 int i,j,min,k,sum=0;
12 lowcost[1]=0;
13 f[1]=1;
14 g[0]=0;
15 for(i=2;i<=m;i++)
16 {
17 lowcost[i]=map[1][i];
18 g[i]=1;//本语句不可以省略
19 }
20 for(i=2;i<=m;i++)
21 {
22 min=65535;
23 for(j=1;j<=m;j++)
24 if(lowcost[j]<=min&&f[j]==0)//寻找与已经生成的最小生成树邻接的边的最小权值
25 {
26 min=lowcost[j];//min是最小权值
27 k=j;//k是最小权值边的终端所对应的数组元素的下标
28 }
29 printf("%d->%d:%d\n",g[k],k,min);//本语句只是为表现出最小生成树的结构,g数组也是为此而定义,可省略该数组
30 sum=sum+min;
31 f[k]=1;//表明f[k]元素已经用完,下次再碰到时直接跳过
32 for(j=1;j<=m;j++)//最重要的一步,不解释
33 {
34 if(map[k][j]<lowcost[j]&&f[j]==0)
35 {
36 lowcost[j]=map[k][j];
37 g[j]=k;
38 }
39 }
40 }
41 return sum;
42 }
43 int main()
44 {
45 while(scanf("%d%d",&m,&n)!=EOF)
46 {
47 int sum=0;
48 int i,j;
49 for(i=0;i<=100;i++)
50 for(j=0;j<=100;j++)
51 map[i][j]=65535;//将map数组中的元素全部置为最大,表示各个节点之间无联系
52 for(i=1;i<=n;i++)
53 {
54 int u,v,w;
55 scanf("%d%d%d",&u,&v,&w);
56 if(map[u][v]>w)//防止出现输入2 3 3,2 3 4这样的情况,所以要比较求出最小权值
57 {
58 map[u][v]=w;
59 map[v][u]=w;
60 }
61 }
62 sum=prim();
63 printf("%d\n",sum);
64 }
65 }
View Code
示例:
输入:
6 10
1 2 6
2 5 3
5 6 6
6 4 2
4 1 5
3 1 1
3 2 5
3 5 6
3 6 4
3 4 5
输出:
15
转载于:https://www.cnblogs.com/kuangdaoyizhimei/p/3244588.html