『算法-ACM 竞赛-最小生成树算法』最小生成树题目总结

2019.9.18 最小生成树知识点总结

1. HDU 4081 Qin Shi Huang’s National Road System（次小生成树-Kruskal）
2. 博主的方法很好，但是有疑问，为什么不能将最多人口的两城市的距离设置为 0，在进行 Prim 操作，求 B 呢？这个将在后续的刷题中体现。
3. POJ 2377 Bad Cowtractors（最大生成树-Kruskal）
4. 裸题，可以用来熟悉算法。
5. HDU 6141 I am your Father!（最小树形图）
6. 朱刘算法，这个还不会，稍后来填坑。
7. CodeForces 609 E.Minimum spanning tree for each edge（最小生成树-Kruskal+在线倍增 LCA）
8. 在线倍增 LCA，等等再回来填坑
9. HDU 2121 Ice_cream’s world II（最小树形图）
10. 朱刘算法
11. HDU 4009 Transfer water（最小树形图）
12. 朱刘算法
13. POJ 1258 Agri-Net（最小生成树-Prim）
14. 最小生成树裸题！
15. POJ 3723 Conscription（最小生成树-Kruskal）
16. 这个题是说招募兵，然后亲密关系会减少招募的花费，这个题一开始的思路是并查集，但是后来想，对于因为亲密关系程度不一样，所以还是得用最小生成树，考虑过是不是要枚举节点，后来明白了，不需要根节点，最小生成树生成后根节点也就确定了，所以就没必要了，直接亲密程度设成负值，一遍最小生成树。
17. POJ 3026 Borg Maze（bfs+最小生成树-Prim）
18. 这个题，是说有一个像史莱姆一样的的怪物，会向四个方向分裂，求分裂的最小次数，也就是说重复的路只算一次，那么我一开始想到的最短路就不对了，因为重复的路径不算，那么也就是说是找的一颗最小生成树，那么需要找到任意两点的距离，但是我看他们只用了一遍 BFS，然后搜了搜题解，发现自己看错了，确实是 N2 遍。
19. POJ 1789 Truck History（最小生成树-Prim）​​​​​​​
20. 最小生成树变形，每个字符串不一样的字符数是距离，然后求最小生成树，字符串判等，暴利即可。
21. POJ 2485 Highways（最小生成树-Prim）
22. 一遍最小生成树，然后标记最大边输出即可。