构造: 构造: 计算最小生成树的第k 计算最小生成树的第k长边
• 可行性。如果d等于第k长边的长度，将去掉前k-1 长的边，最小生成树将被分成k个连通支。由引理， 原图也将被分成k个连通支，满足连通支个数小于 等于k的要求。 • 最优性。如果d小于第k长边的长度，至少会去掉 前k长的边，最小生成树至少被分成k+1个连通支， 原图也至少被分成k+1个连通支，不满足要求。
通过函数top(i)计算顶点i所在子树的根
func top(i:longint):longint; /*计算和返回顶 计算和返回顶 所在并查集的代表顶点*/ 点i所在并查集的代表顶点 所在并查集的代表顶点 { if i<>f[i] Then f[i]←top(f[i]); /*若i非所在并 若 非所在并 查集的代表顶点，则沿f[i]递归 递归*/ 查集的代表顶点，则沿 递归 top←f[i]; /*返回顶点 所在并查集的代表顶点 返回顶点i所在并查集的代表顶点 返回顶点 所在并查集的代表顶点*/ };/*top*/
逆向思维
找到一个最小的d，使得连通支的 个数小于等于卫星设备的数目k。
引理
如果去掉所有长度大于d的边后，最小
生成树被分成k个连通支，那么图也被分 成k个连通支。
证明提示： 1. 反证法 2. 构造回路
证明
用反证法。假设原图被分割成k’(k‘≠k)个连通支，显然k’<k。根 据鸽巢原理,在某一连通支TK’中，最小生成树被分成了至少两部 分，不妨设其为T1，T2。因为T1和T2同属于一个连通支TK’，所 以一定存在x∈T1，y∈T2，w(x，y)≤d。又因为在整个最小生 成树中，所以x到y的路径中一定存在一条权值大于d的边(u，v) （否则x和y就不会分属于T1和T2了），w(x，y)≤d<w(u，v)， 所以把(x，y)加入，把(u，v)去掉，将得到一棵总权值比最小生 成树还小的生成树。这显然是不可能的。所以，原命题成立。 （证毕）
Kruskal程序 程序
Const maxn=200; maxe=maxn*maxn; /*顶点数和边数的上限 顶点数和边数的上限*/ 顶点数和边数的上限 Type edgetype=Record /*边的类型 边的类型*/ 边的类型 x,y,c:longint; /*边权为 的边（x，y）*/ 边权为c的边 边权为 的边（ ， ） end; Var e:Array [1..maxe] of edgetype; /*边集，其中第 条边为 边集， 边集 其中第i条边为 (e[i].x,e[i].y)，该边的权为 ，该边的权为e[i].c*/ n,m,ans:longint; /*顶点数为 ，边数为 顶点数为n，边数为m*/ 顶点数为 f:Array [1..maxn] of longint; /*并查集。其中 为顶点 所在 并查集。 为顶点i所在 并查集 其中f[i]为顶点 并查集的代表顶点，即子树根*/ 并查集的代表顶点，即子树根
计算最小生成树的思维方向： 计算最小生成树的思维方向：为了保证边权
总和最小，必须保证
①、添加(u,v)不能够形成回路、 ②、在保证１的前提下添加权尽可能小的， 这样的边称之为安全边
有两种算法可计算图的最小生成树 ①、Kruskal算法 ②、Prim算法
①、Kruskal算法 Kruskal算法
找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v) 作为安全边，并把它添加到正在生长的森林中。初始时，森林 由单个结点组成的n棵树。
动态生成最小生成树
在一个初始化为空的无向图中，不断加入新边。如果 当前图连通，就求出当前图最小生成树的总权值；否 则，输出-1。 输入输出情况：第1行输入顶点数n和加入的边数k；以 下为2*k行，其中第2*i行输入‘x y c’,表示加入的第i 条边连接顶点x和y，权值为c；第2*i+1行输出回答： 最小生成树的总权值（如果当前图连通），或者-1 （如果当前图不连通）
图的最小生成树
对于一张图进行深度优先搜索或宽 度优先搜索， 度优先搜索，可生成一棵深度优先 搜索树或宽度优先搜索树。 搜索树或宽度优先搜索树。搜索的 出发点不同，生成树的形态亦不同。 出发点不同，生成树的形态亦不同。 在一张有权连通图中， 在一张有权连通图中，各边权和为 最小的一棵生成树即为最小生成树。 最小的一棵生成树即为最小生成树。
初始化
const maxn = 800; /*顶点数的上限 顶点数的上限*/ 顶点数的上限 var pnt:array[1..maxn]of integer;/*顶点 的父顶点为 顶点i的父顶点为 顶点 的父顶点为pnt[i]*/ e, c:array[1..maxn, 0..maxn] of integer; /*边表 ，其中顶点 相连的 边表e，其中顶点i相连的 边表 边数为e[i,0]，第j条边的另一端点为 条边的另一端点为e[i,j]，c为相邻矩阵 为相邻矩阵*/ 边数为 ， 条边的另一端点为 ， 为相邻矩阵 n,k,sum,t:integer; /*顶点数为 新添边数为 ，生成树的总权值为 顶点数为n新添边数为 顶点数为 新添边数为k， sum，边数为 ，边数为t*/ xi,yi,max:integer;/*当前路径的最大边权为 当前路径的最大边权为max,对应边为 对应边为(xi,yi)*/ 当前路径的最大边权为 对应边为 ok:boolean; /*成功标志 成功标志*/ 成功标志 proc Init; /*输入信息 输入信息*/ 输入信息 var i:integer; { readln(n, k); /*输入顶点数和加入的边数 输入顶点数和加入的边数*/ 输入顶点数和加入的边数 fillchar(e,sizeof(e),0);sum←0;t←0; /*边表、生成树的总权值和边数 边表、 边表 初始化*/ 初始化 for i←1 to n do pnt[i]←i; /*n个顶点组成 棵树 个顶点组成n棵树 个顶点组成 棵树*/ };/*Init*/
主算法
按照边权值（c域值）递增的顺序排序边集e； 按照边权值（ 域值）递增的顺序排序边集 ； 域值 For i←1 to n Do f[i]←i; /*建立由 棵树组成的森林，每 建立由n棵树组成的森林 建立由 棵树组成的森林， 棵树包含图的一个顶点*/ 棵树包含图的一个顶点 ans←0; /* 最小生成树的权和初始化为 最小生成树的权和初始化为0*/ For i←1 to m Do Union(e[i].x,e[i].y,e[i].c); /*枚举每条边， 枚举每条边， 枚举每条边 将两个端点分属两棵树的边加入最小生成树*/ 将两个端点分属两棵树的边加入最小生成树 Writeln(ans); 显然, 算法的效率取决于边数m,因此适用与稀疏 显然 Kruskal算法的效率取决于边数 因此适用与稀疏 算法的效率取决于边数 图。
北极通讯网络
北极的某区域共有n座村庄(1 (1≤ 500)， 北极的某区域共有n座村庄(1≤n≤500)，每座村庄的坐标用一对 整数(x y)表示 (x， 表示， 10000。为了加强联系， 整数(x，y)表示，其中 0≤x，y≤10000。为了加强联系，决定在村庄 之间建立通讯网络。通讯工具可以是无线电收发机， 之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星 设备。所有的村庄都可以拥有一部无线电收发机， 设备。所有的村庄都可以拥有一部无线电收发机， 且所有的无线电 收发机型号相同。但卫星设备数量有限， 收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫 星设备。不同型号的无线电收发机有一个不同的参数d 星设备。不同型号的无线电收发机有一个不同的参数d，两座村庄之 间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d 间的距离如果不超过d就可以用该型号的无线电收发机直接通讯， 值越大的型号价格越贵。 值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都 可以直接通讯。 可以直接通讯。 现在有k 100）卫星设备，请你编一个程序， 现在有k台（0≤k≤100）卫星设备，请你编一个程序，计算出应 如何分配这k台卫星设备，才能使所拥有的无线电收发机的d值最小， 如何分配这k台卫星设备，才能使所拥有的无线电收发机的d值最小， 并保证每两座村庄之间都可直接或间接地通讯。请输出最小d值 并保证每两座村庄之间都可直接或间接地通讯。请输出最小d
图的最小生成树满足这个性质
反证法：反设图中存在一棵生成树T，T中的最大边权 小于最小生成树Tmin的最大边权。 令e是Tmin的最大边。e将Tmin分成两个连通分块X和Y。 由于Tmin是最小生成树，那么图中连接X和Y的任意边e’, 其边权都大于等于e的边权——结论1。 而T是图的一棵生成树，那么T中的最大边e’’连接X和 Y，按照假设,e’’的边权小于e的边权。这与结论1矛盾， 因此最小生成树最大边权最小的结论是成立的。 因此只要用Prim或Kruscarl算法求出图的最小生成树 即可。
数据限制：n≤500，k≤100。 K=2——B和C，min(d)=d(A,B)=10。
逆向思维
已知k，求d，比较困难。 已知d，求k，相对简单！
村庄设为顶点，所有可以 互相通讯的村庄连边，边 长为村庄间的距离，构造 一个图。图中卫星设备的 台数k就是图的连通支的个 数，每个连通支内顶点间 的边长不大于d。
通过过程Union(i,j,c)合并顶点i和顶点 j所在的两棵树
现有边权为c的边（i，j）。若该边的两个端点分 属于两棵树，顶点i和顶点j所在子树的根分别为x 和v，则(i,j) 加入最小生成树，合并两棵树（即顶 点i和顶点j所在的并查集）。
proc Union(i,j,c:longint); /*合并 和j所在集合 合并i和 所在集合 所在集合*/ 合并 Var x,y:longint; { x←top(i); y←top(j); /*分别取出顶点 和顶点 所在子 分别取出顶点i和顶点 分别取出顶点 和顶点j所在子 树的根*/ 树的根 if x<>y Then { inc(ans,c);f[y]←x;}; /*若i和j分属于两棵 若 和 分属于两棵 子树，则该边权计入最小生成树的权和，两棵子树合并 子树，则该边权计入最小生成树的权和， */ };/* Union */