首页 > 其他 > 详细

| 959 E

时间:2019-05-19 14:19:15      阅读:174      评论:0      收藏:0      [点我收藏+]

模拟kruskal的过程。每连接两个连通块时,所需的边权值为其中一个连通块的点的个数。

如图

技术分享图片

因此对于n个点,所连接的第(n-1)条边,权值为(n/2),连接了两个点数为(n/2)的连通块。

技术分享图片

技术分享图片
#include<cstdio>
#include<algorithm>
using namespace std;
long long n;
long long ans;
long long x = 1;
int main()
{
    scanf("%lld",&n);
    while(n>1)
    {
        ans+=x*(n/2);
        n-=(n/2);
        x*=2;
    }
    printf("%lld",ans);
    return 0;
}
View Code

 

| 959 E

原文:https://www.cnblogs.com/orange-/p/10889034.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!