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 }

View Code