POJ2485【基础】
题目大意：
N个城镇依次编号为1到N。两个城镇间可以修筑一条高速公路，而且每条高速公路都是直的双向通道。司机可以在一个城镇中从一条高速公路上下来转到另一条高速公路上。以前任意两个城市之间都没有告诉公路。现在要修筑若干条高速公路，让新的路网可以连接每个城市，并且让总的修筑长度最小。求这个最小的修筑长度中最长的一条公路长度。
输入6
第一行是一个整数T，表示有T组测试数据。
每一组测试数据的第一行有一个整数N（3<=N<=500），表示城镇数量。接下来有N行，第i行会包含N个数字，每一行第j个数字表示从第i个城镇到第j 个城镇的距离。这些距离数值范围为[1，63356]。两个测试数据之间有一个空行。T与第一组测试数据之间也有一个空行。
输出：
每一组测试数据输出一行，表示总长度最小的公路网中最长的一条公路的长度。
题解：
裸体的求最小生成树。Prim秒之。
POJ1258【基础】
题目大意：
当选新镇长以后的农夫John要把互联网带到所有的农场。他将在农场之间铺设通道，让通道两端的农场可以共享网络。现在给出所有的农场和农场间的距离，求通讯网所需要铺设的总的距离的最小值。
输入：
有若干组测试数据。每一组数据的第一个数N（3<=N<=100）表示农场数，随后是一个N×N的矩阵，第i行第j列的值表示第i个农场到第j个农场的铺设线路距离。
输出：
每个测试数据输出一行，表示需要铺设总的距离的最小值。
题解：
裸的最小生成树。Prim求之。
我的Prim和Kruskal模板都是从IOI2004国家集训队论文《最小生成树算法及其应用》末尾的模板改写得来的，明显并查集Kruskal比二叉堆Prim好写不止一点。所以以后都用Kruskal了。
POJ1789【基础】
题目大意：
（淦。这是一道可以媲美阅读考试的题。）有很多个7位小写英文字母组成的字符串编号，定义两个字符串之间的距离为两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来，代价为这两个编号之间的距离。现在要出一种“衍生”方案，使得总的衍生代价Q最小，也就是距离之和最小。
输入：
有若干组测试数据。每一组测试数据的开头有一个整数N（2<=N<=1000）表示有多少个字符串编号，接下来的N行每一行有一个编号。当N=0时输入数据组结束。
输出：
每个测试数据组输出一行，文字是“The highest possible quality is
字符串长度最大是多少1/Q.”，Q为总衍生代价的最小值。
题解：
赤裸裸的最小生成树。每一个编号是一个节点，一种“衍生”是一条路径。Kruskal解决。
POJ1861【基础】
题目大意：
公司需要架设新的网络。有N个网络中枢，其中有些中枢之间可以用网线连接起来。新的网络架设完毕后，需要可以从某一个网络中枢访问到另外任意一个网络中枢。由于有不同长度的网线可以选择，而且网线越短越便宜，所以新的网络中需要令所有网线中最长的单根网线最短。不是所有的网络中枢都可以直接连接，但是你可以知道哪些网络中枢之间是可以互联的。
输入：
输入包含多组测试数据。每个测试数据第一行为两个整数N（2<=N<=1000）和M （1<=M<=15000），分别表示网络中枢数和连接数。网络中心依次从1到N编号。接下来的M行每一行有三个整数，依次是可连接的两个网络中枢的编号和连接需要的网线长度（<=10^6）。每两个网络中枢之间最多只有一条线路，每个网络中枢不能与自己连接。测试数据保证总能让网络连通。
输出：
对每组测试数据，首先输出连接方案中最长的单根网线的长度的最小值；然后输出你的设计方案：先输出一个整数P，代表所使用的网线数目；然后输出P 对顶点，表示每根网线所连接的集线器编号，整数之间用空格或换行符隔开。题目采取Special Judge。
题解：
由最小生成树的原理可知，符合条件的一个设计方案必定是最小生成树。故直接求最小生成树即可。另外需要注意的是，这题不是严格要求的最小生成树，允许有环的出现。（其实直接Kruskal都可以了）
POJ3522【基础】
题目大意：
给出一个无向图，求一棵生成树，令生成树中权值最大的边与权值最小的边的差最小。
输入：
有若干组测试数据。
每一组测试数据第一行有两个整数n、m（1<=n<=100,1<=m<=n*(n-1)/2），表示这个无向图中有n个点和m条边。接下来有m行，每一行有三个整数u、v、w，表示一条边两端的点编号和边的权。n=m=0时测试数据结束。
输出：
每一组测试数据输出一行。如果生成树存在，输出生成树中权值最大的边与权值最小的边的差的最小值。如果生成树不存在，输出-1。
题解：
这种求最大最小值差的，在其他网络流的题目里很常见，而我们常用的方法是枚举：二分枚举区间宽度和枚举区间起点。这题用这种方法也可以，不过时间太久。最小生成树有几个性质，其中有一个是同一张图的最小生成树可以有多个，但是两个最小生成树的最大边权和最小边权都是相等的。因此，如果一棵生成树的最小边权已经确定了，那么其最大边权也一定是确定了的。因此我们只要枚举最小边权就好了。
POJ1679【基础】
题目大意：
给出一个无向图，求其最小生成树是否唯一。
输入：
输入的第一行有一个整数，表示有多少组测试数据。
每一组测试数据的第一行有两个整数n、m（1<=n<=100，1<=m<=n*(n-1)/2），表示图有n个点和m条边，边没有重复的。接下来有m行，每一行有三个整数u、v、w，表示一条边两端的点编号和边的权。
输出：
每一组测试数据输出一行：如果存在唯一的最小生成树，输出最小生成树的边权和，否则输出“Not Unique!”。
题解：
这道题的思路很常规，先求一次最小生成树，然后枚举其每一条边，在不选择此边的情况下求一次最小生成树，看看边权和是否和第一次求的最小生成树的边权和相等即可。
………………你以为这样就完了？！没完！
首先，题目很坑爹地木有指出，如果图不连通的情况下应该输出什么。Discuss 里有人说应该输出0，我这么做WA了。个网上AC了的代码对拍一下，发现
人家压根就不判断能不能连通！但是如果不判断能否连通的话Kruskal在这里有一个小的漏洞，那就是如果有边的权为0并且是原来的最小生成树的边，那么把此边去掉以后不能生成了，但是返回的结果是一样的。所以最后还是要判断连通性。第三，就是标准代码库里qsort的不稳定性，对同一组数据排序，几个关键字相同的条目的顺序是会变的，我在这里也栽了跟头，所以要把排序抽出来只进行一次。
啊啊啊啊写代码还是要再细心一点啊啊啊啊啊！
POJ2395【基础】
题目大意：
Bessie要调查其他农场中干草存储情况。一共有N（2<=N<=2000）个农场依次编号为1到N，Bessie从1号农场出发，会从M（1<=M<=10000）条双向道路中选择一些道路来从一个农场到达另一个农场，这些道路的长度都不大于
1,000,000,000。有些农场之间有不止一条道路。所有农场总会通过一条路或者别的路连接到1号农场。Bessie需要走遍所有的农场。
Bessie要自己带水上路。它知道自己在每个单位长度路程上的耗水量，又因为它可以在任何一个农场补充水，所以它只希望知道在调查路途中它最少需要带多少水。
假设Bessie会选择道路让它需要带的水最少，为此它可以走某些回头路。
输入：
第一行是两个用空格分隔的整数N和M。
下面的M行每一行包含三个整数，表示一条道路连接的两个农场的编号和这条道路的长度。
输出：
一行，一个整数，表示在调查途中所经过的最长的路径的长度。
题解：
一开始这题很容易被误解为求单源最短路，然后算各最短路中的最长路径。但是由于Bessie可以走回头路，所以对于某一个最优解决方案，它走的边一定都是单条边长度最小的，以确保它走过的边中的长度最长的边的长度最小。所以符合Kruskal算法的原理，也就是求最小生成树。
POJ2377【基础】
题目大意：
Bessie被雇佣去为John农夫建立一个廉价的互联网络系统。John有N
（2<=N<=1000）个谷仓依次编号为1到N。已知有M（1<=M<=20000）条可能建立链接的通道，每条通道建立的费用C范围为1<=C<=100000。John想用最少的钱建立网络系统，甚至不想付钱给Bessie。
察觉到了John的邪恶用心，Bessie决定把事情搞砸，也就是建立的互联网络系统要花最多的钱。为了不让John看出Bessie在搞鬼，所有的谷仓应该要可以互联，并且不可以出现环，否则John会很轻易地看出Bessie在搞鬼。
输入：
第一行是两个用空格分开的整数N和M
下面M行每一行分别是三个空格分隔的整数，分别是每条可用连接两端的两个谷仓编号和修建费用。
输出：
一行，建立一个最大花费的网络连接树所需要花费的钱。如果有某些谷仓无法被连接，输出-1。
题解：
将最小生成树改成最大生成树，对与Kruskal而言仅仅是在快排那里改了两个符号。另外此题可能出现无法全部点连通需要判断，即在所有边被枚举完了以后，如果入树点少于N，即为未连通。
POJ2421【基础】
题目大意：
有N（3<=N<=100）个村庄依次编号为1到N。现在需要扩充道路网络，令所有的村庄都被连接到一起（也就是从任意一个村庄都应该能走到其他任意一个村庄）。在现有的道路网络中，有若干条道路是已经被修筑好了的，你应该尽量利用这些道路。这些已经修建好了的道路是已知的。修筑道路的总长度应该尽可能小。
输入：
第一行一个整数N。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。