最小生成树【完结】

2 利用Prime算法，把最小生成数的边存储在ans数组里面，最后对ans按照从大到小排序，最后的ans就是ans[n-1].
3 由上面我们知道通过卫星相连的站点的距离可以很大，那么我们通过最小生成树求出来的最大的权值的边就可以当成是卫星来连接的，排序后那么扣除n条边，那么最后的ans就是ans[n-1];

点击查看代码

第六题 uva 10068Audiophobia

点击打开uva 10068

思路：

1 现在城市污染很严重，除了平常的污染外还有什么声音污染。现在有c个城市，s个街道，每一个街道有一个声音的分贝值。现在由于从某一点到另外一点有很多条路径，现在要求我们找到一条路径中使得这条路径上的最大的声音分贝是所有可达路径中最小的。如果没有输出“no path”，否则额输出这个最小值。

2 利用kruskal的算法的思想，我们先把所有的要求的路径保存起来。那么利用kruskal开始生成树，每加入一个连通分量的我们就去判断所有要求的路径中是否已经在同一个连通分量里面并且没有求过，因为我们知道如果两个点在这一次合并后变成同一个连通分量，那么这两个点的最短路已经形成，并且由于kruskal的性质上一次加入的边长度肯定比下一次加入的小。所以可以知道这个路径要求的ans 就是当前的这个边的权值（具体好好想想，表达能力实在有限）。

点击查看代码

第七题 uva 10099The Tourist Guide

点击打开uva 10099

思路：

1 有一个旅游团现在去出游玩，现在有n个城市，m条路。由于每一条路上面规定了最多能够通过的人数，现在想问这个旅游团人数已知的情况下最少需要运送几趟

2 从题目可以知道从起始点到达终点的路径可能会有很多条，但是现在要求运送的次数最少，那么就是要满足每一次的运送都能够达到最多的人数。那么这就转变成求在满足条件的所有路径中所有边最小值中的最大值。那么只要按照求解最小生成树的过程，把排序改成按照大的排序然后在生成树的时候判断目标点是否在同一个连通分支里面，如果在同一个连通分支里面那么ans就是当前这条边的长度。最后求几次的时候在判断一下是否可以整除

3 注意：由于导游每一次都要跟着车走，那么实际上能够载的人数是要减1的。

第八题 hdu 1875 畅通工程续

思路：模板题

第九题 hdu 1879 继续畅通工程

思路：模板题

第十题 poj 1861 Network

思路：模板题

第十一题 poj 1258Agri-Net

点击打开poj 1258

思路：模板题

点击查看代码

第十二题 poj 1287 Networking

点击打开poj 1287

思路：模板题

点击查看代码

第十三题 poj 1789Truck History

点击打开poj 1789

思路：模板题

点击查看代码

第十四题 poj 2377Bad Cowtractors

点击打开poj 2377

思路：模板题

点击查看代码

第十五题 poj 3625Building Roads

点击打开poj 3625

思路：

1 由于点有1000，如果要用kruskal的话最少有1000000条边，所以我么选择用peime算法
2 题目中的点的坐标最大值为10^6，那么如果在平方一下的话会超过int，所以在求两个点之间的距离的时候用在前面乘上一个1.0这样就表示的double从而不会超过int了。
3 题目中的说了，要用64位的浮点数，所以选择用long double 。输出的时候是“%0.2Lf”。

点击查看代码

第十六题 poj 1679The Unique MST

点击打开poj 1679

思路：

1 判断最小生成树是否是唯一的，那就可以去判断次小生成树是否大于最小生成树。这里就涉及到了次小生成树的求法
2 求解次小生成树：
step 1. 先用prim求出最小生成树T.
在prim的同时，用一个矩阵max[u][v] 记录在T中连结任意两点u,v的唯一的
路中权值最大的那条边的权值. (注意这里).
这是很容易做到的，因为prim是每次增加一个结点s, 而设已经标号了的结点
集合为W, 则W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.
step 1 用时 O(V^2).
step 2. 枚举所有不在T中的边uv, 加入边uv则必然替换权为max[u][v]的边

点击查带代码

第十七题 poj 2485 Highways

点击打开poj 2485

思路：模板

点击查看代码

第十八题 poj 2395 Out of Hay

点击打开poj 2395

思路：模板题

点击查看代码

第十九题 poj 1751 Highways

点击打开poj 1751

思路：

1 只要按照prime的思路求出所有的边，然后输出的时候判断是否是已经建好的即可。
2 可能出现已经把所有的边都建好的情况，这个时候不用输出

点击查看代码

第二十题 poj 2728Desert King

点击打开poj 2728

思路：最优比例生成树

1问题描述：
已知一个完全图，每条边有两个参数（dis和c），求一棵生成树，使(∑xi×ci)/(∑xi×disi)最小，其中xi当第i条边包含在生成树中时为1，否则为0。

2处理方法：
1迭代法
假设rate为当前比率，以ci-rate×disi作为各边的权重，使用Prim算法构造最小生成树，再对该最小生成树求(∑xi×ci)/(∑xi×disi)更新rate，可证明rate可收敛且收敛值即为所求。
2二分法
在一个精度范围内（以1e-6为例），二分查找[0,maxRate]之间的值rate，使(z=∑xi×ci-rate×∑xi×disi)==0，可证明该值即为所求。其中xi为以ci-rate×disi作为各边权重时，使用Prim算法所构造的最小生成树。在二分搜索过程中若z>0，则将区间上移(low=mid)，否则将区间下移(high=mid)。

3解题思路及相关证明：
1问题转化：
给定一个rate，z(rate)=∑xi×ci-rate*∑xi×disi，xi为一棵生成树使(∑xi×ci-rate*∑xi×disi)的值最小(下面会介绍求此生成树的方法)，则rate=(∑xi×ci-z(rate))/( ∑xi×disi)，令rateNex=(∑xi×ci)/( ∑xi×disi)。
若z(rate)>0，则肯定不存在一棵生成树使rate=(∑yi×ci)/( ∑yi×disi)，即rate值无效，且有rateNex >rate；
若z(rate)<0，则我们可得到一个有效比率rateNex，且rateNex<rate；
若z(rate)==0，则rateNex==rate，且rate有效。
因此，如果有且仅有一个rate使z(rate)==0，又由题目所求的最小比率的存在性（有限节点的完全图其生成树只有有限个）可知，该rate值即为所求。

2下面证明其存在性和唯一性：
存在性：对于题目所求的最小比率rateMin，由上面的分析必有z(rateMin)=0，又由该最小比率的存在性可知，至少存在一个有效的比率rate使z(rate)=0；
唯一性：只要证明z(rate)函数的单调性即可：
对于两个比率rate1<rate2，
z(rate1)-z(rate2)= (∑xi×ci-rate1*∑xi×disi)-(∑yi×ci-rate2*∑yi×disi)
<=(∑yi×ci-rate1*∑yi×disi)-(∑yi×ci-rate2*∑yi×disi)
=(rate2-rate1)* ∑yi×disi>0
因此，z(rate)为单调递减函数。从而也就证明了满足z(rate)==0的比率rate的唯一性。
由上面的分析，我们就将问题转化为求解比率rate使z(rate)==0。

3求解：有两种方法对该问题进行求解：迭代法和二分法。
A、迭代法：由上面的分析可知：
当 z(rate)>0时，rate值无效，而rateNex有效且z(rateNex)<=0；
当z(rate)<0时，rateNex<rate，又z(rate)为单调递减函数，故0>=z(rateNex)>z(rate)。
故迭代过程向z(rate)==0收敛，又由有限节点的完全图其生成树只有有限个可知迭代次数必为有限值。

B、二分法：在定出一个搜索范围和精度之后(以[0,MAXRATE]为例)，我们就可以使用二分法进行搜索：对于当前的搜索区间[low,high]，mid=(low+high)/2，根据z(mid)的值及z(rate)的增减性，对搜索区间进行更新：
若z(mid)>0，上调区间，使low=mid+1；
若z(mid)<0，下调区间，使high=mid-1；
从而在经过有限次搜索之后便能找到所求比率。

3、求解生成树xi使(∑xi×ci-rate*∑xi×disi)的值最小的方法：∑xi×ci-rate*∑xi×disi=∑xi(ci+rate×disi)，从而问题转化为以ci+rate×disi为边的权重，求解最小生成树，对于完全图，可使用prim算法，其复杂度只与节点数有关。

点击查看代码

第二十一题 poj 3522Slim Span

点击打开poj 3522

思路：

题目要求的是找到一个生成树使得生成树中“最大边-最小边”的值最小。如果这个图有n个点，那么这个生成树有n-1条边。那么现在就是考虑怎么去枚举这些生成树，我们想到了跟边有关的就是kruskal。我们只要按照边的大小排好序，然后去枚举最小的边的值，因为每一个生成树都要有n-1条边，所以只要枚举从0～(m-n+1)即可，然后按照求解最小生成树的方法去求每一个生成树，最后求出ans。

点击查看代码

第二十二题 poj 3723Conscription

点击打开poj 3723

思路：

1 首先我们应该区分开男孩和女孩，只要将男孩的编号加上女孩的个数n，这样就可以做到男孩和女孩的编号是不同的。
2 题目中说了如果两个人有关系，并且其中一个人已经被选了那么选择另外一个人的时候只要10000-d即可。所以这就涉及到了两个人的关系问题，那么自然的想到了并查集来保存关系图。所以这n+m个人最后就可以被分到s个集合里面，每一个集合里面的人都是有关系的。那么这样我们只要求出s个集合的最小生成树相加，然后在加上s*10000（没有关系的时候选择一个人要10000），即为最后的答案。

点击查看代码

第二十三题 poj 1639Picnic Planning

点击打开poj 1639

思路：

1. 先求出最小 m 度限制生成树：
原图中去掉和 V0 相连的所有边，得到 m 个连通分量，则这 m 个连通分量必须通过 v0 来连接，所以，在图 G 的所有生成树中 dT(v0)≥m 。也就是说，当 k<m 时，问题无解。对每个连通分量求一次最小生成树，对于每个连通分量 V’ ，用一条与 V0 直接连接的最小的边把它与 V0 点连接起来，使其整体成为一个生成树。于是，我们就得到了一个 m 度限制生成树，不难证明，这就是最小 m 度限制生成树。

2. 由最小 m 度限制生成树得到最小 m+1 度限制生成树：
连接和 V0 相邻的点 v ，则可以知道一定会有一个环出现（因为原来是一个生成树），只要找到这个环上的最大权边（不能与 v0 点直接相连）并删除，就可以得到一个 m+1 度限制生成树，枚举所有和 V0 相邻点 v ，找到替换后，增加权值最小的一次替换 (当然，找不到这样的边时，就说明已经求出) ，就可以求得 m+1 度限制生成树。如果每添加一条边，都需要对环上的边一一枚举，时间复杂度将比较高（但这个题数据比较小，所以这样也没问题，事实上，直接枚举都能过这个题），这里，用动态规划解决。设 Best(v) 为路径 v0—v 上与 v0 无关联且权值最大的边。定义 father(v) 为 v 的父结点，由此可以得到动态转移方程： Best(v)=max(Best(father(v)),ω(father(v),v)) ，边界条件为 Best[v0]=-∞ (因为我们每次寻找的是最大边，所以 -∞ 不会被考虑) ，Best[v’]=-∞| (v0,v’)∈E(T) 。这个可以用dfs做到

3. 当 dT(v0)=k 时停止(即当 V0 的度为 k 的时候停止)，但不一定 k 的时候最优。

点击查看代码

第二十四题 hdu 4463Outlets

点击打开hdu 4463

思路：

1 题目要求的找到n个商店组成n-1条边，并且要求耐克和苹果商店肯定要相连，求最短长度
2 很明显的最小生成树的模板题，由于要求耐克和苹果的商店要在一起那么就要把这两个商店编号合并到同一个集合，然后在利用kruskal计算。

点击查看代码

分享到：