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

　　这道题和刚才的题出自同一个方法，似乎用prim算法更好，不知道你刚才的代码还留着吗？其实刚才的代码稍加改动，这道题就能过了，下面来分析一下这道题与刚才的题的异同点，首先输入一定是不同的，要输入一个矩阵，所以这里要改一下；还有这道题只求和，不求每一条边，这可是一个福利，不用像刚才一样麻烦了，总之，废话不多说，AC代码呈上：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int n,a[1000],q,ans,map[1000][1000];
 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)
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             ans+=large.cost;
44         }
45     }
46 }
47 int main()
48 {
49     tree s;
50     scanf("%d",&n);
51     for(int i=1;i<=n;i++)
52     for(int j=1;j<=n;j++)
53     {
54         scanf("%d",&map[i][j]);
55         s.start=i;
56         s.end=j;
57         s.cost=map[i][j];
58         t.push(s);
59         if(i!=j)
60         e++;
61     }
62     kruskal();
63     printf("%d",ans);
64     return 0;
65 }

　　具体就不怎么介绍了，这也是一道纯模板题，如果你想练手，可以先写一写下面这道题。

T3：

【题目描述】

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000。

【输入】

第一行：农场的个数，N（3≤N≤100）。

第二行..结尾:后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。

?

【输出】

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

【输入样例】

4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0

【输出样例】

28

　　怎么样，你写出来了吗？下面是AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int n,ans);
64     return 0;
65 }

　　有没有发现什么？和T2一模一样的代码竟然在T3就过了，我猜出这道题的是为了让我们再手敲一遍代码加深理解，既然这道题是披着T3皮的T2，那就不解释了，直接看一道变形。

牛刀小试

T4：

【题目描述】

某个局域网内有n(n≤100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)≤1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。

【输入】

第一行两个正整数n k

接下来的k行每行三个正整数i j m表示i,j两台计算机之间有网线联通，通畅程度为m。

【输出】

一个正整数，Σf(i,j)的最大值。

【输入样例】

5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2

【输出样例】

8

　　照之前的套路小编题也不看就猜到了要干什么，潇洒的把T1和T2结合在一起，稍微一改输入输出，差点就提交了，幸亏最后试了一下输入样例，什么，竟然之前的模板不灵了！小编看了看题，才恍然大悟，也不过如此，这道题求的是产生回路的边的和，那么就加产生回路的边好了。AC代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int n,ans;
 8 struct tree{
 9     int start;
10     int end;
11     int cost;
12 };
13 tree T[1000];
14 bool operator < (const 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             
44         }
45         else ans+=large.cost;//注意这里有变
46     }
47 }
48 int main()
49 {
50     tree s;
51     scanf("%d%d",&e);
52     for(int i=1;i<=e;i++)
53     {
54         scanf("%d%d%d",&s.cost);
55         if(s.start>s.end) swap(s.start,s.end);
56         t.push(s);
57     }
58     kruskal();
59     printf("%d",ans);
60     return 0;
61 }

　　这道题轻松一变就过了，可以说这四道题是捆绑在一起的，一道过了，四道稍变就全过。其实例题一共有四道，但是为什么没有把第四到放进来讲呢？这是因为这道题是到大水题。

大水题

T5：

【题目描述】

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。

给出每个人的孩子的信息。

输出一个序列，使得每个人的后辈都比那个人后列出。

【输入】

第1行一个整数N（1≤N≤100），表示家族的人数；

接下来N行，第I行描述第I个人的儿子；

每行最后是0表示描述完毕。

?

【输出】

输出一个序列，使得每个人的后辈都比那个人后列出；

如果有多解输出任意一解。

?

【输入样例】

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

【输出样例】

2 4 5 3 1

（编辑：ASP站长网）