第三部分 第一题

《线网建设》

——通信王国里的修路大师（Kruskal最小生成树）

第一幕：通信王国

1、很久很久以前。

程序大陆上，有一个十分发达的国家——

通信王国。

王国里有很多座通信基站。

每座基站都有自己的坐标，例如：

① (1,0) ② (3,2) ③ (5,1) ④ (2,4)

2、国王希望：

任意两座基站，都能够互相通信。

但是……

修建线路可是要花钱的！

线路越长，花的钱越多。

更麻烦的是：

超过 L 米的线路根本修不了。

于是国王说：

"请你帮我设计一套最省钱的建设方案。"

这就是今天这道题。

第二幕：读懂题目

1、输入：

n

个点。

2、每个点：

(x,y)

坐标。

3、两个点之间距离

就是：

√((x1-x2)²+(y1-y2)²)

但是：

只有

距离≤L

才能修。

4、最后要求：

所有点连通。

总代价最小。

5、如果不能连通：

输出

Impossible

6、举一个最简单的例子

（1）例如：

A B C

三座城市。

（2）距离：

A-B 2 A-C 5 B-C 3

画出来：

A 2 / \5 / \ B -- 3 --C

（3）有三条路。

如果全部修：

总代价：

2+5+3=10

太浪费。

（4）其实修：

A-B B-C

总代价：

5

所有城市仍然连通。

这就是：

最小生成树（MST）

第三幕：什么叫生成树？

1、有的同学会问：

为什么叫生成树？

（1）假设有：

4个城市。

全部修：

A-----B |\ /| | \ / | | / \ | |/ \| C-----D

里面有很多圈。

（2）其实：

有些路可以拆掉。

（3）最后：

A | B | C | D

或者：

A / \ B C | D

（4）只要：

所有点连通。

没有环。

这就是：

生成树。

2、为什么要最小？

（1）因为：

生成树有很多种。

（2）我们要：

总代价

最小。

（3）所以：

叫

最小生成树（Minimum Spanning Tree）

第四幕：怎样才能花的钱最少？

这就是整道题最关键的问题。

（1）假设现在有这些边：

长度 8 2 5 1 9 3

（2）如果你是国王。

你会先修哪条？

（3）当然：

最便宜！

所以：

第一条原则：

先修最短的路。

（4）于是排序：

变成：

1 2 3 5 8 9

是不是就结束了？

不是！

第五幕：为什么不能一直修？

（1）来看：

A / \ 2 3 / \ B --- 1 ---C

（2）已经修了：

A-B B-C

现在：

A和C

其实已经能到达。

（3）如果：

再修

A-C

会怎样？

（4）就出现：

环。

A / \ B---C

这条边：

完全浪费。

（5）所以：

第二条原则：

形成环的边不能修。

（6）于是：

Kruskal算法

终于出现了。

第六幕：Kruskal算法

整个算法只有四句话。

1、第一步

把所有边算出来。

例如：

5个点。

两两之间：

1-2 1-3 1-4 ... 4-5

全部记录。

本题就是：

for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)

枚举所有点对。

2、第二步

距离超过L。

不能修。

直接不要。

if(dx*dx+dy*dy>l*l) continue;

为什么不用：

sqrt(...)

因为：

开方慢。

比较平方即可。

3、第三步

剩下边。

按照长度排序。

例如：

1 2 3 5 8

越来越长。

4、第四步

从小到大加入。

如果：

不会形成环。

修。

否则：

跳过。

直到：

修了：

n-1

条边。

结束。

5、Kruskal流程图

所有边 ↓ 排序 ↓ 最短边 ↓ 形成环？ ↓ 否 ↓ 加入 ↓ 继续 ↓ 已经加入 n-1 条？ ↓ 结束

是不是很简单？

第七幕：怎样判断有没有形成环？

1、这是八级最重要的数据结构：

并查集（Union Find）

2、假设：

（1）开始：

A B C D

四个人。

互相不认识。

（2）编号：

A B C D

（3）现在修：

A-B

于是：

A和B

成为一家人。

（4）再修：

B-C

现在：

ABC

是一家。

（5）最后：

如果：

修：

A-C

会怎样？

（6）并查集一查：

发现：

他们已经是一家。

说明：

形成环。

不能修。

（7）这就是：

并查集最大的作用：

快速判断两个点是否已经连通。

第八幕：为什么最后要判断

t==n-1

（1）生成树有一个性质：

n个点，一定只有n-1条边。

例如：

5个点。

一定：

4

条边。

（2）否则：

要么：

不连通。

要么：

有环。

（3）因此：

最后：

如果：

t<n-1

说明：

还有点没连上。

输出：

Impossible

这就是题目的要求。

第九幕：完整算法流程

整道题其实就是下面这一张图。

读入坐标 │ ▼ 枚举所有点对 │ ▼ 距离≤L？ │ 否│继续 ▼ 加入边集 │ ▼ 按照长度排序 │ ▼ 依次枚举边 │ ▼ 并查集判断 是否形成环？ │ 是│跳过 ▼ 加入生成树 │ ▼ 统计总代价 │ ▼ 加入边==n-1？ │ 是│输出答案 否│Impossible

第十幕：为什么这题选择Kruskal，而不是Prim？

1、有的同学都会问：

Prim也能求最小生成树呀？

答案是：

当然能。

2、但是本题：

（1）先要判断：

距离≤L

还要：

枚举所有点对。

天然就生成了一张：

边表（Edge List）

（2）而Kruskal最喜欢：

边表。

所以：

写起来，最自然。

第十一幕：参考程序：

1、官方参考程序：

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; // 最多500个点 const int N = 510; // 最多边数 // 两两连边，最多约 N*N 条 const int E = N * N; // n：基站数量 // l：允许修建线路的最大长度 int n, l; // 每个基站的坐标 int x[N], y[N]; // p：保存边的编号 // u：边的起点 // v：边的终点 int p[E], u[E], v[E]; // 当前共有多少条边 int cnt; // 并查集数组 // f[i]表示i的父节点 // 开始全部为0，表示自己就是集合代表 int f[N]; // t表示已经加入最小生成树的边数 int t = 0; // d保存每条边的长度 double d[E]; // 最终答案（最小生成树总长度） double ans = 0; ////////////////////////////////////////////////////// // 并查集——寻找祖先（带路径压缩） ////////////////////////////////////////////////////// int getf(int u) { // 如果没有父亲 // 自己就是祖先 if (f[u] == 0) return u; // 路径压缩 return f[u] = getf(f[u]); } ////////////////////////////////////////////////////// // 排序函数 // 按照边长从小到大排序 ////////////////////////////////////////////////////// bool cmp(int a, int b) { return d[a] < d[b]; } int main() { ////////////////////////////////////////////////// // 输入 ////////////////////////////////////////////////// cin >> n >> l; // 输入每个点坐标 for (int i = 1; i <= n; i++) cin >> x[i] >> y[i]; ////////////////////////////////////////////////// // 枚举所有边 ////////////////////////////////////////////////// for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { // 两点横坐标差 int dx = x[i] - x[j]; // 两点纵坐标差 int dy = y[i] - y[j]; // 如果距离超过L // 这条边不能修 // // 注意： // 比较平方即可 // 不需要sqrt() if (dx * dx + dy * dy > l * l) continue; // 新增一条边 cnt++; // 第cnt条边 p[cnt] = cnt; // 起点 u[cnt] = i; // 终点 v[cnt] = j; // 保存真正距离 d[cnt] = sqrt(dx * dx + dy * dy); } } ////////////////////////////////////////////////// // 所有边按长度排序 ////////////////////////////////////////////////// sort(p + 1, p + cnt + 1, cmp); ////////////////////////////////////////////////// // Kruskal ////////////////////////////////////////////////// for (int i = 1; i <= cnt; i++) { // 当前边编号 int id = p[i]; // 当前边两个端点 int pu = u[id]; int pv = v[id]; ////////////////////////////////////////////////// // 判断是否已经连通 ////////////////////////////////////////////////// if (getf(pu) == getf(pv)) continue; ////////////////////////////////////////////////// // 加入最小生成树 ////////////////////////////////////////////////// // 边数+1 t++; // 累加长度 ans += d[id]; ////////////////////////////////////////////////// // 合并两个集合 ////////////////////////////////////////////////// f[getf(pu)] = getf(pv); } ////////////////////////////////////////////////// // 判断是否成功生成树 ////////////////////////////////////////////////// // n个点 // 最小生成树必须有n-1条边 if (t == n - 1) printf("%.2lf\n", ans); else printf("Impossible\n"); return 0; }

2、教学版

#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; const int MAXN = 505; //======================= // 一条边 //======================= struct Edge { int u; // 起点 int v; // 终点 double w; // 长度 }; //======================= // 所有边 //======================= vector<Edge> edge; //======================= // 并查集 //======================= int parent[MAXN]; //======================= // 查找祖先（路径压缩） //======================= int Find(int x) { if(parent[x]==x) return x; return parent[x]=Find(parent[x]); } //======================= // 合并两个集合 //======================= void Union(int x,int y) { x=Find(x); y=Find(y); parent[x]=y; } //======================= // 排序规则 //======================= bool cmp(Edge a,Edge b) { return a.w<b.w; } int main() { int n,L; cin>>n>>L; vector<pair<int,int>> point(n+1); // 输入坐标 for(int i=1;i<=n;i++) { cin>>point[i].first>>point[i].second; parent[i]=i; // 初始化并查集 } // 建边 for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { int dx=point[i].first-point[j].first; int dy=point[i].second-point[j].second; if(dx*dx+dy*dy>L*L) continue; Edge e; e.u=i; e.v=j; e.w=sqrt(dx*dx+dy*dy); edge.push_back(e); } } // 排序 sort(edge.begin(),edge.end(),cmp); double ans=0; int cnt=0; // Kruskal for(auto e:edge) { if(Find(e.u)==Find(e.v)) continue; Union(e.u,e.v); ans+=e.w; cnt++; // 已经形成生成树，可以提前结束 if(cnt==n-1) break; } if(cnt==n-1) cout<<fixed<<setprecision(2)<<ans; else cout<<"Impossible"; }

第十二幕：程序详细解析步骤

1、我们先不要写程序

而是先画流程图。

这道题应该先画：

输入坐标 │ ▼ 枚举所有点之间距离 │ ▼ 超过L？ 是─────────┐ │ │ │跳过 │保留 ▼ ▼ 加入边集 │ ▼ 所有边排序 │ ▼ Kruskal算法 │ ▼ 输出答案

2、 第一件事情——设计一条边

（1）官方程序用了四个数组：

u[] v[] d[] p[]

对于初学者不太好理解。

（2）我们可以把它们合成一个结构体。

struct Edge { int u; // 起点编号 int v; // 终点编号 double w; // 边长 };

是不是舒服多了？

（3）一条边就是：

Edge 里面放： 起点 终点 长度

（4）例如：

Edge 1 3 2.36

（5）就是：

1 -------- 3 长度2.36

3、我们需要很多很多边

（1）当然不能只存一条。

于是：

vector<Edge> edge;

（2）就是建立：

边仓库

以后：

算出来一条边。

就放进去。

（3）例如：

1——2 ↓ push_back() ↓ 仓库

（4）再来一条：

2——5 ↓ push_back() ↓ 仓库

以后：

所有边都在这里。

4、怎样比较两条边？

（1）排序的时候。

sort不知道：

什么叫

"短"。

（2）所以我们告诉它。

bool cmp(Edge a,Edge b) { return a.w<b.w; }

（3）意思就是：

谁短。

谁排前面。

（4）例如：

4.3 2.1 8.5 1.6

排序以后：

1.6 2.1 4.3 8.5

这就是Kruskal第一步。

5、 并查集重新写

（1）官方程序使用：

f[]

我们改个名字。

int parent[505];

是不是一下就知道：

父亲

什么意思。

（2）初始化：

1 2 3 4 5

每个人：

父亲都是自己。

for(int i=1;i<=n;i++) parent[i]=i;

（3）画出来：

1 ↓ 1

2 ↓ 2

......

谁也不认识谁。

6、Find函数

（1）这里也是我们教学的重点。

int Find(int x) { if(parent[x]==x) return x; return parent[x]=Find(parent[x]); }

（2）为什么这样写？

举个例子。

（3）原来：

1 ↓ 2 ↓ 5

（4）以后：

再找：

1。

程序：

一路找：

1 ↓ 2 ↓ 5

找到：

5。

（5）然后：

顺便把：

1 ↓ 5

以后：

不用绕路了。

这就叫：

路径压缩。

7、 Union函数

（1）官方写了一句：

f[getf(x)]=getf(y);

有的同学看起来有点累。

（2）我们写成函数。

void Union(int x,int y) { x=Find(x); y=Find(y); parent[x]=y; }

一下就清楚了。

（3）第一步：

找到两个家长。

（4）第二步：

让：

x家

搬到：

y家

结束。

8、 建边

（1）这里是整个程序最好理解的一部分。

for

枚举：

所有点。

① ② ③ ④

（2）两两之间：

计算距离。

如果：

≤L

说明：

可以修。

加入：

edge

（3）代码写成：

Edge e; e.u=i; e.v=j; e.w=sqrt(...); edge.push_back(e);

（4）是不是比：

u[] v[] d[]

好理解？

9、 Kruskal真正开始

（1）排序：

sort(edge.begin(),edge.end(),cmp);

（2）这一句。

就是：

最短 ↓ 最长

（3）然后：

开始修路。

for(auto e:edge)

意思：

一条一条拿出来。

（4）例如：

第一条：

1——3

第二条：

2——5

......

（5）然后判断：

if(Find(e.u)==Find(e.v))

什么意思？

就是：

看看：

是不是已经认识。

（6）进行判断：

认识：

跳过。

不认识：

修路。

Union() ans+=e.w;

10、 判断是否提前结束

（1）提前结束条件：

已经修了 n-1 条边。

（2）生成树永远：

n个点 ↓ n-1条边

这是数学性质。

（3）所以：

if(cnt==n-1)

立即结束。

还能快一点。

第十三幕：这道题考察了哪些知识？

这是一道典型的图论综合题。它把几何建图 + 边集构造 + 排序 + 并查集 + Kruskal 最小生成树完整串联了起来，是八级具有代表性的编程题之一。

最后，送给同学们一句 Kruskal 的口诀

先建边，再排序；
边最短，优先取；
并查集，判成环；
不是一家就合并；
修满n-1条边，最小生成树就完成！

只要记住这五句话，今后遇到绝大多数Kruskal 最小生成树的题目，都能迅速建立正确的解题思路。