PTA数据结构与算法题目集(中文) 7-10
7-10 公路村村通 (30 分)
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤）和候选道路数目M（≤）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−，表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
题目分析:一道图的最小生成树算法的基础题 利用Prim或Kruskal算法来解决最小生成树问题 稠密图用Prim算法 稀疏图使用Kruskal算法 注意收录顶点在找到后就立刻进行 这样就不会对对角线上的元素进行判断 1 #define _CRT_SECURE_NO_WARNINGS
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<malloc.h>
5 #define MAXVERTEXNUM 1000
6 #define INIFITY 65535
7
8 typedef struct ENode* Edge;
9 struct ENode
10 {
11 int V1, V2;
12 int Weight;
13 };
14
15 typedef struct GNode* Graph;
16 struct GNode
17 {
18 int Nv;
19 int Ne;
20 int G[MAXVERTEXNUM][MAXVERTEXNUM];
21 };
22
23 Graph BuildGraph(int VertexNum)
24 {
25 Graph Gra = (Graph)malloc(sizeof(struct GNode));
26 Gra->Nv = VertexNum;
27 Gra->Ne = 0;
28 for(int i=1;i<=Gra->Nv;i++)
29 for (int j = 1; j <=Gra->Nv; j++)
30 {
31 if (i == j)
32 Gra->G[i][j] = 0;
33 else
34 Gra->G[i][j] = INIFITY;
35 }
36 return Gra;
37 }
38
39 void Insert(Edge E, Graph Gra)
40 {
41 Gra->G[E->V1][E->V2] = E->Weight;
42 Gra->G[E->V2][E->V1] = E->Weight;
43 }
44
45 Graph CreateGraph()
46 {
47 int N, M;
48 scanf("%d%d", &N, &M);
49 Edge E = (Edge)malloc(sizeof(struct GNode));
50 Graph Gra = BuildGraph(N);
51 Gra->Ne = M;
52 for (int i = 0; i < M; i++)
53 {
54 scanf("%d%d%d", &(E->V1), &(E->V2), &(E->Weight));
55 Insert(E, Gra);
56 }
57 return Gra;
58 }
59
60 int IsEdge(Graph Gra, int V, int W)
61 {
62 return Gra->G[V][W] < INIFITY;
63 }
64
65 int Dist[MAXVERTEXNUM];
66 int Path[MAXVERTEXNUM];
67 int Collected[MAXVERTEXNUM];
68 int Sum;
69 int FindMin(Graph Gra)
70 {
71 int MinDist = INIFITY;
72 int Min = -1;
73 for (int i = 1; i <=Gra->Nv; i++)
74 if (!Collected[i] && Dist[i] < MinDist)
75 {
76 MinDist = Dist[i];
77 Min = i;
78 }
79 return Min;
80 }
81 void Prim(Graph Gra,int V)
82 {
83 Dist[V] = 0;
84 Path[V] = -1;
85 Collected[V] = 1;
86 for (int i = 1; i <= Gra->Nv; i++)
87 {
88 Dist[i] = Gra->G[V][i];
89 Path[i] = V;
90 }
91 while (1)
92 {
93 int Min = FindMin(Gra);
94 if (Min ==-1)
95 break;
96 Collected[Min] = 1;
97 Dist[Min] = 0;
98 Sum += Gra->G[Path[Min]][Min];
99 for (int i = 1; i <=Gra->Nv; i++)
100 {
101 if (!Collected[i] && IsEdge(Gra, Min, i))
102 if (Gra->G[Min][i] < Dist[i])
103 {
104 Dist[i] = Gra->G[Min][i];
105 Path[i] = Min;
106 }
107 }
108 }
109 }
110
111 int main()
112 {
113 Graph Gra = CreateGraph();
114 Prim(Gra,1);
115 int Flag =1;
116 for (int i = 1; i <= Gra->Nv; i++)
117 if (!Collected[i])
118 Flag = 0;
119 if (Flag)
120 printf("%d", Sum);
121 else
122 printf("-1");
123 return 0;
124 }