BZOJ 1821: [JSOI2010]Group 部落划分 Group 并查集 贪心 二分

我们把所有边排个序,然后从大到小选,并查集维护连联通性,然后选入n – k条边之后,就形成了k个联通块,剩下边中可以选的最大值就是所求的答案。一定要注意是剩下边中可以选择的,也就是连接两个联通块的边的长度才是答案,开始直接输出的下一条边的值,这个答案可能偏小,因为它可能位于联通块内。

还有一种做法,就是我们二分一下,然后在把小于这个长度的边全连上,看有几个联通块。

发表评论