← 返回目录

算法笔试模拟题精解之“Codancer 的旅行”

第 50 / 74 卷日期：

算法笔试模拟题精解之“Codancer 的旅行”

贡献者 | 猿圈、黄信旭

简介：根据样例数据从 1 到 2 的花费为 1，从 1 到 3 的花费为 2，从 2 到 3 的

花费为 1，花费都小于 3，因此总共有三种方案。

题目描述

题目等级：困难

知识点：二分查找 / 并查集 / 贪心

查看题目：Codancer 的旅行

期末考试终于结束啦，Codancer 开始了他的旅行。

现在整个地图上由 n 个城市，这些城市之间有 n-1 条道路相连，每条道路都有

一个距离，并且保证整个图是连通的，即这个地图可以看作是一棵树。

现在假设 Codancer 要从城市 A 到城市 B，那么他的路费就是从 A-B 的路径上

边权最大的边的权值 wmaxx 元。

现在 Codancer 有 k 元，他想知道他能选择那些 (A,B) 并且 A<B 使得 codancer

能够到达。

第一行输入两个正整数 n 和 k，代表城市的个数和 Codancer 现有的资金数目，

接下来 n-1 行每行三个数 u,v,w, 代表城市 u 和城市 v 之间有一条长度为 w 的道路。

（1<=n<=100000,1<=k<=1000,1<=u,v<=n,1<=w<=1000）

输出 codancer 可选择的方案数。

示例 1

输入：

3

3

[[1,2,1],[2,3,1]]

输出：

3

注意

Codancer 可以选择从 :

1->2

1->3

2->3

解题方法一

根据样例数据从 1 到 2 的花费为 1，从 1 到 3 的花费为 2，从 2 到 3 的花费为

1，花费都小于 3，因此总共有三种方案。

图 130-1
图 130-1

首先按照边权将这些边从小到大排序，使用并查集记录当前连通块内的最大的

边权。

当 u 和 v 连接起来的时候，假设此时的联通块大小为 cnt, 则答案应该加上

cnt*(cnt-1)/2，同时应该减去之前 u 和 v 单独为连通块的方案数。

令 ans[i] 为最大边权为第 i 条时构成的连通块的方案数，那么对于 k，二分查找

最大的小于等于 k 的下标 id，最终答案就是 ans[id]。

时间复杂度为：O(nlog(n))

解题方法二

虽然题中给出的是一个树形结构，但是解题时和树的关系不是很大。

题中指出从城市 A 到 B 的路费是从 A-B 的路径上边权最大的边的权值 wmaxx

元。可以理解成对于权值大于现有资金数目 k 的边，codancer 不能通过，其他边可

以任意通过。所以原始的树形结构被不能通过的边分割成了多个子区域。每个子区域

没的任意两个城市是可以互相到达的。每个子区域内方案数为 C(n, 2)，n 为子区域

内城市个数。

对于子区域的计算可以考虑从底向上合并的形式。创建一个 1*n 的数组 a，数

组的每个位置代表一个城市，每个位置的内容代表这个城市所在的子区域。初始化时

a[i] = i。遍历时，选择可以通过的边，把两个边对应的城市所属子区域合并（修改成

同样的数字）即可。

时间复杂度 O(2n) 第一遍判断每个城市属于哪个子区域。第二遍计算每个子区

域城市个数，并用 C(n, 2) 求和。

空间复杂度 O(n)

看完之后是不是有了答题思路了呢，快来练练手吧：Codancer 的旅行

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”