【图论2-3】最小生成树

题单介绍

试想在一个平原国家中有若干城市,要建立若干高速公路,这些高速公路可以建成直线,连 接在两个城市之间。如何规划这些高速公路使建造距离总和最短,就是一种典型的最小生成树问 题。 树是一种特殊的图,具有很多特殊的性质。生成树问题研究的是将图中的所有顶点保留,但 只选择图中的部分边,得到一棵树(也就是图的生成树)的问题。最小生成树则是在这些生成树 中,边权之和最小的生成树。可以使用 $Prim$ 算法或者 $Kruskal$ 算法求解最小生成树。 对应进阶篇第 11 章。 ![](https://ipic.luogu.com.cn/69s1yt.png)

题目列表

  • 【模板】最小生成树
  • 买礼物
  • [BJWC2010] 严格次小生成树
  • 营救
  • 口袋的天空
  • [USACO08OCT] Watering Hole G
  • [NOIP2013 提高组] 货车运输
  • 逐个击破
  • Shichikuji and Power Grid
  • [APIO2008] 免费道路
  • Power Tree