题目：
某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标，
使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路相连，只要互相间接通过快
速路可达即可)。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修通的状态。
现请你编写程序，计算出全地区畅通需要的最低成本：
1 #include "stdio.h"
2 /*
3 某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标，
4 使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路相连，只要互相间接通过快
5 速路可达即可)。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修通的状态。
6 现请你编写程序，计算出全地区畅通需要的最低成本：
7 输入格式:
8
9 输入的第一行给出村庄数目NN(1\le N \le 1001≤N≤100)；随后的N(N-1)/2N(N?1)/2行对应村庄间道路的成本及修建状态：
10 每行给出4个正整数，分别是两个村庄的编号(从1编号到NN)，此两村庄间道路的成本，以及修建状态 — 1表示已建，0表示未建。
11 输出格式:
12
13 输出全省畅通需要的最低成本。
14 输入样例:
15
16 4
17 1 2 1 1
18 1 3 4 0
19 1 4 1 1
20 2 3 3 0
21 2 4 2 1
22 3 4 5 0
23 输出样例:
24
25 3
26 */
27 #define MAX 101
28 #define INFINITY 10000 //表示极大值
29 //prim算法从顶点入手
30 struct Edge{
31 int adjvex;//U中 记录最小边在U中的那个顶点
32 int lowcost;//U中 最小边的权值
33 }closedge[MAX];//辅助数组，记录从U到V-U具有最小代价的边
34 void MinSpanTree_Prime(int G[MAX][MAX] ,int n)
35 {
36 int sum=0;
37 int i,j;
38 //用prim算法从第1个顶点
39 closedge[1].lowcost = -1;//将第1个顶点并入到U中
40 for(j=2;j<=n;j++)
41 {
42 //对于V-U中的顶点j,初始化closedge[j]
43 if(G[j][1]<closedge[j].lowcost)
44 {
45 closedge[j].adjvex = 1;
46 closedge[j].lowcost = G[j][1];
47
48 }
49 }
50 printf("实现全地区畅通需要的最低成本的道路有:\n");
51 for(i=1;i<n;i++)
52 {//共n-1轮，每轮找出最小边输出，赋-1更新
53 int k = INFINITY;
54 for( j=1;j<=n;j++)
55 {
56 if(closedge[j].lowcost!=-1)
57 {
58 k = j;break;
59 }
60 }
61 for( j=1;j<=n;j++)
62 {//求U和V-U之间最小的权值在V-U中的顶点的位置
63 if(closedge[j].lowcost!=-1)
64 if(closedge[j].lowcost<closedge[k].lowcost)
65 k = j;
66 }
67 sum += closedge[k].lowcost;
68 printf("(%d,%d)",closedge[k].adjvex,k);//输出最小边
69 closedge[k].lowcost = -1;//将顶点k加入集合U中
70 for( j=1;j<=n;j++)
71 { //根据k结点更新数组元素代价
72 if(G[j][k]<closedge[j].lowcost)
73 {
74 closedge[j].adjvex = k;
75 closedge[j].lowcost = G[j][k];
76 }
77 }
78
79 }
80 printf("\n最低成本为：%d",sum);
81 }
82
83 int main(){
84 int n,m;
85 int i,j;
86 int G[MAX][MAX];
87 //G先初始化为无穷
88 for( i=1;i<MAX;i++)
89 {
90 for( j=1;j<MAX;j++)
91 {
92 G[i][j] = INFINITY;
93 }
94 }
95 for( i=0;i<MAX;i++)
96 {
97 closedge[i].lowcost = INFINITY;
98 }
99 scanf("%d",&n);
100 m = n*(n-1)/2;
101 for( i=0;i<m;i++)
102 {
103 int t1,t2,t3,t4;
104 scanf("%d",&t1);
105 scanf("%d",&t2);
106 scanf("%d",&t3);
107 scanf("%d",&t4);
108 if(t4==1)
109 t3 = 0;
110 G[t1][t2] = t3;
111 G[t2][t1] = t3;
112 }
113 MinSpanTree_Prime(G,n);
114 return 0;
115 }
转播
