【数据结构】 最小生成树（四）——利用kruskal算法搞定例题×3+

　　在这一专辑（最小生成树）中的上一期讲到了prim算法，但是prim算法比较难懂，为了避免看不懂，就先用kruskal算法写题吧，下面将会将三道例题，加一道变形，以及一道大水题，水到不用高级数据结构，建树，画图，最短路径什么的，统统不需要。废话不多说，直接看题：

例题精讲

T1：

【题目描述】

有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？

【输入】

n（城市数，1<≤n≤100）

e（边数）

以下e行，每行3个数i,j,wiji,j,wij，表示在城市i,j之间修建高速公路的造价。

【输出】

n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。

【输入样例】

5 8
1 2 2
2 5 9
5 4 7
4 1 10
1 3 12
4 3 6
5 3 3
2 3 8

【输出样例】

1  2
2  3
3  4
3  5

　　看完之后有思路吗？这题肯定简单，这是一道纯模板题，只不过输出有点麻烦。总之，先来回忆一下kruskal算法原理：首先需要找到图中的一条最短的边，如果它不与最小生成树集合中的其他边产生回路，那么就加入这条边至集合中，上次小编写的很草率，只是一个伪代码（伪代码如下），这次的题目小编会写成正式代码；接着，输出又是一个麻烦事，这就需要分析样例了，先好好看一看样例，你发现了吗？左边的数总小于右边的数，下面的第一个数总比上面的第一个数大，当然，如果第一个数一样大，那么就按第二个数从小到大排序。依据这个规律，接着，就来看一看AC代码吧。

 1 //假设MST[]是最小生成树的集合，cnt表示是存入集合的边数 
 2 while(cnt<n-1)//共有n-1条边
 3 {
 4     在图中找出最短的一条边;
 5     if(添加这条边不产生回路) 
 6     {
 7         加入MST集合;
 8         cnt++; 
 9     } 
10 }

//伪代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int n,e,a[1000],k,p,q;
 8 struct tree{
 9     int start;
10     int end;
11     int cost;
12 };
13 tree T[1000];
14 bool operator < (const tree& a,const tree& b)//按cost的值从小到大排序
15 {
16     return a.cost>b.cost;
17 }
18 bool cmp(tree a,tree b)//这个排序方式就是上面所说的关系
19 {
20     if(a.start==b.start)
21     return a.end<b.end;
22     return a.start<b.start;
23 }
24 priority_queue<tree>t;
25 inline int find(int x)//并查集 26 {
27     if(x==a[x]) return x;
28     else return a[x]=find(a[x]);
29 }
30 void kruskal()
31 {
32     for(int i=1;i<=n;i++)//并查集初始化
33     a[i]=i;
34     tree large;
35     for(int i=1;i<=e;i++)
36     {
37         large=t.top();//获取最小边
38         t.pop();
39         if(find(large.start)!=find(large.end))//如果不产生回路
40         {
41             p=find(large.start);q=find(large.end);
42             a[q]=p;
43             T[++k]=large;//加入到集合中
44         }
45     }
46     sort(T+1,T+k+1,cmp);//按规律排序，否则顺序不对
47     for(int i=1;i<=k;i++)
48     printf("%d %d \n",T[i].start,T[i].end);
49 }
50 int main()
51 {
52     tree s;
53     scanf("%d%d",&n,&e);
54     for(int i=1;i<=e;i++)
55     {
56         scanf("%d%d%d",&s.start,&s.end,&s.cost);
57         if(s.start>s.end) swap(s.start,s.end);
58         t.push(s);
59     }
60     kruskal();
61     return 0;
62 }

//AC代码

　　这个代码虽然看起来很长，但是效率很高，如果用数组来存储，代码确实精简了，看起来确实易懂了，但是很浪费时间，每一次的最小边都要花O（n）的时间去寻找，如果用堆（优先队列），直接询问队顶元素就可以了。如果你并不清楚用着结构体的优先队列，就一定不会理解以下这段代码的意思，这段代码表示按cost的值进行排序，因为结构体中有三个元素，不这么写就无法按你的心意排序。

14 bool operator < (const tree& a,const tree& b)
15 {
16     return a.cost>b.cost;
17 }

T2:

【题目描述】

学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。

当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。

现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。

【输入】

第一行为整数n（2≤n≤100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。

【输出】

一个整数，表示最小的连接费用。

【输入样例】

3
0 1 2
1 0 1
2 1 0

【输出样例】

2

（编辑：ASP站长网）