还是畅通工程

题目描述：

    某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入：

    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
    当N为0时，输入结束，该用例不被处理。

输出：

    对每个测试用例，在1行里输出最小的公路总长度。

样例输入：

3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

样例输出：

3
5

---

该题和前面的“畅通工程”都是属于最小生成树的问题，前面用的并查集的prime算法，现在用一下克鲁斯卡尔算法。其中，排序算法用的是标准C里面的qsort函数。

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 int visited[101];
 5 struct Edge{
 6     int vertex1;
 7     int vertex2;
 8     int cost;
 9 };
10 
11 
12 int cmp(const void *a, const void *b)
13 {
14     Edge *e1 = (Edge*) a;
15     Edge *e2 = (Edge*) b;
16     return e1->cost - e2->cost;
17 }
18 
19 Edge edges[5000];
20 int main()
21 {
22     int n;
23     int count;
24     int costs;
25     while (cin >> n && n != 0)
26     {
27         int counts = n * (n - 1) / 2;
28         count = 0;
29         costs = 0;
30         for (int i = 0; i <= n; i++)
31             visited[i] = 0;
32         for (int i = 0; i < counts; i++)
33         {
34             cin >> edges[i].vertex1 >> edges[i].vertex2 >> edges[i].cost;
35         }
36 
37         qsort(edges, counts, sizeof(Edge), cmp);
38 
39         for (int j = 0; j < counts; j++)
40         {
41             if ((visited[edges[j].vertex1] == 0 || visited[edges[j].vertex2] == 0) && count< n-1)
42             {
43                 costs += edges[j].cost;
44                 visited[edges[j].vertex1] = 1;
45                 visited[edges[j].vertex2] = 1;
46                 count++;
47             }
48         }
49         cout << costs << endl;
50     }
51     
52     return 0;
53 }

 

还是畅通工程

原文：http://www.cnblogs.com/tgycoder/p/5017506.html