在这一专辑（最小生成树）中的上一期讲到了prim算法，但是prim算法比较难懂，为了避免看不懂，就先用kruskal算法写题吧，下面将会将三道例题，加一道变形，以及一道大水题，水到不用高级数据结构，建树，画图，最短路径什么的，统统不需要。废话不多说，直接看题：
1.例题精讲
T1：
1348：【例4-9】城市公交网建设问题
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 2094 通过数: 650
【题目描述】
有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？
【输入】
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代码吧。
//假设MST[]是最小生成树的集合，cnt表示是存入集合的边数
while(cnt<n-)//共有n-1条边
{
在图中找出最短的一条边;
if(添加这条边不产生回路)
{
加入MST集合;
cnt++;
}
}
//伪代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int n,e,a[],k,p,q;
struct tree{
int start;
int end;
int cost;
};
tree T[];
bool operator < (const tree& a,const tree& b)//按cost的值从小到大排序
{
return a.cost>b.cost;
}
bool cmp(tree a,tree b)//这个排序方式就是上面所说的关系
{
if(a.start==b.start)
return a.end<b.end;
return a.start<b.start;
}
priority_queue<tree>t;
inline int find(int x)//并查集 {
if(x==a[x]) return x;
else return a[x]=find(a[x]);
}
void kruskal()
{
for(int i=;i<=n;i++)//并查集初始化
a[i]=i;
tree large;
for(int i=;i<=e;i++)
{
large=t.top();//获取最小边
t.pop();
if(find(large.start)!=find(large.end))//如果不产生回路
{
p=find(large.start);q=find(large.end);
a[q]=p;
T[++k]=large;//加入到集合中
}
}
sort(T+,T+k+,cmp);//按规律排序，否则顺序不对
for(int i=;i<=k;i++)
printf("%d %d \n",T[i].start,T[i].end);
}
int main()
{
tree s;
scanf("%d%d",&n,&e);
for(int i=;i<=e;i++)
{
scanf("%d%d%d",&s.start,&s.end,&s.cost);
if(s.start>s.end) swap(s.start,s.end);
t.push(s);
}
kruskal();
return ;
}
//AC代码
这个代码虽然看起来很长，但是效率很高，如果用数组来存储，代码确实精简了，看起来确实易懂了，但是很浪费时间，每一次的最小边都要花O（n）的时间去寻找，如果用堆（优先队列），直接询问队顶元素就可以了。如果你并不清楚用着结构体的优先队列，就一定不会理解以下这段代码的意思，这段代码表示按cost的值进行排序，因为结构体中有三个元素，不这么写就无法按你的心意排序。
14 bool operator < (const tree& a,const tree& b)
15 {
16 return a.cost>b.cost;
17 }
T2:
1349：【例4-10】最优布线问题
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 1228 通过数: 733
【题目描述】
学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。
当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。
现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。
【输入】
第一行为整数n（2≤n≤100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
【输出】
一个整数，表示最小的连接费用。
【输入样例】
3
0 1 2
1 0 1
2 1 0
【输出样例】
2
这道题和刚才的题出自同一个方法，似乎用prim算法更好，不知道你刚才的代码还留着吗？其实刚才的代码稍加改动，这道题就能过了，下面来分析一下这道题与刚才的题的异同点，首先输入一定是不同的，要输入一个矩阵，所以这里要改一下；还有这道题只求和，不求每一条边，这可是一个福利，不用像刚才一样麻烦了，总之，废话不多说，AC代码呈上：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int n,e,a[],k,p,q,ans,map[][];
struct tree{
int start;
int end;
int cost;
};
//tree T[1000];
bool operator < (const tree& a,const tree& b)
{
return a.cost>b.cost;
}
bool cmp(tree a,tree b)
{
if(a.start==b.start)
return a.end<b.end;
return a.start<b.start;
}
priority_queue<tree>t;
inline int find(int x)
{
if(x==a[x]) return x;
else return a[x]=find(a[x]);
}
void kruskal()
{
for(int i=;i<=n;i++)
a[i]=i;
tree large;
for(int i=;i<=e;i++)
{
large=t.top();
t.pop();
if(find(large.start)!=find(large.end))
{
p=find(large.start);q=find(large.end);
a[q]=p;
ans+=large.cost;
}
}
}
int main()
{
tree s;
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
scanf("%d",&map[i][j]);
s.start=i;
s.end=j;
s.cost=map[i][j];
t.push(s);
if(i!=j)
e++;
}
kruskal();
printf("%d",ans);
return ;
}
具体就不怎么介绍了，这也是一道纯模板题，如果你想练手，可以先写一写下面这道题。
T3：
1350：【例4-11】最短网络(agrinet)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 1054 通过数: 711
【题目描述】
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过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代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int n,e,a[],k,p,q,ans,map[][];
struct tree{
int start;
int end;
int cost;
};
//tree T[1000];
bool operator < (const tree& a,const tree& b)
{
return a.cost>b.cost;
}
bool cmp(tree a,tree b)
{
if(a.start==b.start)
return a.end<b.end;
return a.start<b.start;
}
priority_queue<tree>t;
inline int find(int x)
{
if(x==a[x]) return x;
else return a[x]=find(a[x]);
}
void kruskal()
{
for(int i=;i<=n;i++)
a[i]=i;
tree large;
for(int i=;i<=e;i++)
{
large=t.top();
t.pop();
if(find(large.start)!=find(large.end))
{
p=find(large.start);q=find(large.end);
a[q]=p;
ans+=large.cost;
}
}
}
int main()
{
tree s;
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
scanf("%d",&map[i][j]);
s.start=i;
s.end=j;
s.cost=map[i][j];
t.push(s);
if(i!=j)
e++;
}
kruskal();
printf("%d",ans);
return ;
}
有没有发现什么？和T2一模一样的代码竟然在T3就过了，我猜出这道题的是为了让我们再手敲一遍代码加深理解，既然这道题是披着T3皮的T2，那就不解释了，直接看一道变形。
2.牛刀小试
T4：
1391：局域网(net)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 1072 通过数: 658
【题目描述】
某个局域网内有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代码如下：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int n,e,a[],k,p,q,ans;
struct tree{
int start;
int end;
int cost;
};
tree T[];
bool operator < (const tree& a,const tree& b)
{
return a.cost>b.cost;
}
bool cmp(tree a,tree b)
{
if(a.start==b.start)
return a.end<b.end;
return a.start<b.start;
}
priority_queue<tree>t;
inline int find(int x)
{
if(x==a[x]) return x;
else return a[x]=find(a[x]);
}
void kruskal()
{
for(int i=;i<=n;i++)
a[i]=i;
tree large;
for(int i=;i<=e;i++)
{
large=t.top();
t.pop();
if(find(large.start)!=find(large.end))
{
p=find(large.start);q=find(large.end);
a[q]=p; }
else ans+=large.cost;//注意这里有变
}
}
int main()
{
tree s;
scanf("%d%d",&n,&e);
for(int i=;i<=e;i++)
{
scanf("%d%d%d",&s.start,&s.end,&s.cost);
if(s.start>s.end) swap(s.start,s.end);
t.push(s);
}
kruskal();
printf("%d",ans);
return ;
}
这道题轻松一变就过了，可以说这四道题是捆绑在一起的，一道过了，四道稍变就全过。其实例题一共有四道，但是为什么没有把第四到放进来讲呢？这是因为这道题是到大水题。
3.大水题
T5：
1351：【例4-12】家谱树
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 826 通过数: 568
【题目描述】
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。
【输入】
第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
这道题怎么办？似乎找不到和最小生成树的关系，和图似乎有点关系，可是怎么写呢？这又是一个迷，先看代码再解释：
#include<iostream>
#include<cstdio>
using namespace std;
int n,a[][],ans[],cnt,w[],k,minn;bool vis[]={false};
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==) break;w[i]++;
}
for(int i=;i<=n;i++)
{
minn=,k=;
for(int j=;j<=n;j++)
{
if(vis[j]==true) continue;
if(w[j]<minn)
{
k=j;
minn=w[j];
}
}
vis[k]=true;ans[++cnt]=k;
for(int j=;j<=n;j++)
{
if(vis[j]==true) continue;
for(int l=;l<=n;l++)
if(a[j][l]==k) w[j]--;
}
}
for(int i=cnt;i>=;i--)
printf("%d ",ans[i]);
return ;
}
对，你没有看错，它虽然身处最小生成树中，但是却不需要高级数据结构，说白了就是个找规律题，小编也是瞎猫碰见死耗子，随便一脑洞大开就AC了，当然，也欢迎用最小生成树写出的大佬评论感受，下面来讲一讲小编找出的规律：首先，题目告诉要把父辈排在子辈前面，小编想到了用并查集，但是貌似写不出来，于是小编就猜想是不是儿子越多，辈分就越高，那么如果儿子一样多又该怎么处理呢？接着，小编想了各种方法处理，最后突然想到可以让他们减少儿子，那又怎么减呢？把已经定位好辈分的人从剩下人的儿子中抹掉，假装其他人都失去了这个儿子。那么是应该先挑小辈呢？还是先挑长辈呢？当然是先挑小辈，因为比较好选，优先选长辈会出现很多奇怪的状况，小编亲手试过，有了这个大思路，小编就以试试的心态写出了这个代码，没想到竟然过了，这道题不需要用树，不需要图，不需要最小生成树竟然可以过，纯找规律，真是道大水题。
原本小编还是一知半解的，写了几道题以后终于弄明白了，建议大家也可以写一写。
4.附测评网站：
5.局域网(net)
专栏：