『算法-ACM 竞赛-最小生成树算法』最小生成树知识点回顾

2019.9.17 最小生成树知识点回顾

• POJ 1797 Heavy Transportation（最大生成树-Prim）

  • 最大生成树，方法模仿最小生成树，每次选最大边进行操作，即可。

• HDU 5723 Abandoned country（最小生成树 Kruskal+树形 DP）

  • 未解决等待树形 DP，再回头来看这个题目。

• HDU 5624 KK’s Reconstruction（最小生成树-Kruskal）

  • 这个题是让所求最小生成树的最大值与最小值相差最小，对于一棵最小生成树，当他的最小值确定后，他的最大值也就确定了，这样我们可以从小枚举最小值，求最小生成树，进而得到解。

• GYM 100712 F.Travelling Salesman（最小生成树-Kruskal）

  • 裸题，求最小生成树的最大边权，先用 prim 或者 Kruskal 求一遍最小生成树，选边时记录一下最后一条选的边即可。

• CodeForces 733 F.Drivers Dissatisfaction（最小生成树-Kruskal+在线倍增法）

  • 这个题是说每个边都有权值 Vi，可以花费 Si 使得边权减少 1，最多花费 S，问生成最小的成树的权值和为多少？

  • 

  • 思路是先求一个最小生成树（见上图），对于一条边来说，如果他减少产生的效果最好，那么 S 的花费都应该花费在一条边上，我们可以从最小的 Si 开使枚举，如果第 i 条边在树上，就可以直接计算，如果不在树上，必然构成一个环，如下图，那么必然要删去换上的最大值。用 LCA 维护，可以用倍增做，但是我太明白这个倍增是怎么回事，但是倍增是用来优化时间复杂度的，所以，先知道思想，倍增后面再看。

• HDU 1863 畅通工程（最小生成树-Kruskal）

  • 裸的最小生成树的题目

• HDU 1875 畅通工程再续（最小生成树-Kruskal）

  • 这个题目，是说两个岛的距离不能少于 10 米，也不能大于 100 米才能建桥，求每米花费一元，最小花费。这个题先求任意两岛的欧氏距离，符合条件建边。然后最小生成树，裸题。

• HDU 1879 继续畅通工程（最小生成树-Kruskal）

  • 这个题是说有道路已经修建了，求最小生成树，那么已经修建花费为 0，权值设为 0，最小生成树。

• HDU 2489 Minimal Ratio Tree（dfs+最小生成树-Prim）

  • 他这个题是 DFS 写的，这个题是明显的 0/1 线性规划，可以二分比值求解。

• HDU 4081 Qin Shi Huang’s National Road System（次小生成树-Kruskal）

这个题，有点类似 LCA，还是插边，找环，删边。

POJ 2377 Bad Cowtractors（最大生成树-Kruskal）

裸题