AcWing 走廊泼水节
2021-02-07 13:14
阅读：555
- 最小生成树。
思考库鲁斯卡尔的构造过程。先按边权大小排序，每次取一条边，如果边两端的点不在一个集合，就连这条边。那么对于此题，因为是完全图。如果边两段的点不在一个集合，那么两个集合会产生的边数是集合A的点数 * 集合B的点数。那么我们要构造的边就是（点数 * 集合B的点数 - 1）。边权显然必定是此边的边权 + 1。
那么并查集维护就行。（顺带一提，并查集路径压缩和按秩合并可以一起用..
评论
亲，登录后才可以留言！