【基础练习】【并查集】codevs2796 最小完全图题解

男娘i 2022-08-09 17:56 39阅读 0赞

题目描述 Description

若一个图的每一对不同顶点都恰有一条边相连，则称为完全图。

最小生成树MST在Smart的指引下找到了你，希望你能帮它变成一个最小完全图（边权之和最小的完全图）。

注意：必须保证这个最小生成树MST对于最后求出的最小完全图是唯一的。

输入描述 Input Description

第一行一个整数n，表示生成树的节点数。

接下来有n-1行，每行有三个正整数，依次表示每条边的顶点编号和边权。

（顶点的边号在1-n之间，边权<231）

输出描述 Output Description

一个整数ans，表示以该树为最小生成树的最小完全图的边权之和。

样例输入 Sample Input

4

1 2 1

1 3 1

1 4 2

样例输出 Sample Output

12

数据范围及提示 Data Size & Hint

30%的数据：n<1000；

100%的数据：n≤20000，所有的边权<231。

用克鲁斯卡尔做，读入边然后跑最小生成树，只不过不检查每条边的端点是否属于两个集合（因为本来读入的就是最小生成树，当然在两个集合） 而是统计当前两个集合的元素数size 然后每次加边时 ans+=(sz\[x\]\*sz\[y\]-1)\*(e\[i\].w+1);即可，因为此时左右两个集合都是完全图 但两个集合互不连通 要想让他们完全联通且保证加入的边严格最小 就要让两边集合元素两两连一条边（当前边除外） 权值为当前最小边权+1

应该很好理解

下面讲一下部分分怎么拿 这里以codevs这道题的数据为标准（我们校内胡测数据更强= =）

LCA做法：画图不难发现，对于每两个点，如果要在他们中间连一条边且不能属于最小生成树，那么这条边权最少要是这两个点从最小生成树上连通经过的最长的边+1

那么好办了，我们做一个LCA即可 每次查找两点之间的最长边 ans+=最长边权+1

这个算法的致命缺陷是，由于数据规模大，而LCA需要枚举所有点对，所以会T

codevs过6个点 我们自己的数据只过了3个点

实际上分析可以发现，LCA做法重复计算了很多状态 比如如果E是D的儿子且和A分属两个子树 那么我们从D与A的值即可推E 却重复计算了很多状态

其实仔细想想 这题如果空间开大些 还可以用DP

BFS/DFS做法 不说了 枚举找即可= = codevs20分 我们的数据全T

那么正解代码

//copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    #include
           
             #include
            
        
          typedef long long ll; using namespace std; const ll maxn=100000+10; struct node { ll u,v,w; bool operator < (node nb) const { return w

`——初闻征雁已无蝉，百尺楼高水接天`

发表评论取消回复

表情：

评论列表（有 0 条评论，39人围观）

还没有评论，来说两句吧...

相关阅读

相关【基础练习】【并查集】codevs2796 最小完全图题解

题目描述 Description 若一个图的每一对不同顶点都恰有一条边相连，则称为完全图。最小生成树MST在Smart的指引下找到了你，希望你能帮它变成一个最小完全图（边

男娘i/ 2022年08月09日 17:56/ 0 赞/ 40 阅读

相关【基础练习】【差分】codevs1242 布局题解

题目描述 Description 当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍

青旅半醒/ 2022年08月09日 17:40/ 0 赞/ 287 阅读

相关【基础练习】【二分图匹配】【匈牙利算法】codevs1022 覆盖题解

题目描述 Description 有一个N×M的单位方格中，其中有些方格是水塘，其他方格是陆地。如果要用1×2的矩阵区覆盖（覆盖过程不容许有任何部分重叠）这个陆地，那么最多可

清疚/ 2022年08月09日 15:52/ 0 赞/ 277 阅读

相关【基础练习】【贪心】codevs2612 最优分解方案题解

题目描述 Description 为了迎接圣诞，信息学兴趣小组的同学在辅导老师的带领下，举办了一个盛大的晚会，晚会的主要内容是做游戏。经过第一轮的游戏，不少同学将会获得圣诞特

约定不等于承诺〃/ 2022年08月09日 06:17/ 0 赞/ 345 阅读

相关【基础练习】【SPFA】codevs1557 热浪题解

题目描述 Description 德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer

﹏ヽ暗。殇╰゛Y/ 2022年08月09日 03:29/ 0 赞/ 107 阅读

相关【基础练习】【模拟】codevs1704 卡片游戏题解

题目描述 Description 桌面上有一叠牌，从第一张牌(即位于顶面的牌)开始从上往下依次编号为1~n.当至少还剩两张排时进行一下操作：把第一张牌扔掉，然后把新的第一张牌

川长思鸟来/ 2022年08月09日 02:21/ 0 赞/ 325 阅读

相关【基础练习】【模拟】codevs1053 笨小猴题解

题目描述 Description 笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这

ゝ一纸荒年。/ 2022年08月08日 15:48/ 0 赞/ 256 阅读

相关【基础练习】【栈】codevs2058 括号匹配题解

这道题目就不多说了非常经典的栈练习左括号压栈，右括号比较布尔变量判断即可曾经写过一到类似的表达式求值博客上有可以参考这道题目的最后一个点非常坑不知道哪里

朱雀/ 2022年08月08日 06:57/ 0 赞/ 311 阅读

相关【日常学习】【并查集+map】codevs2639 约会计划题解

然而我竟然让诸城一中悲剧机房的C++能够编译了··· 直接上题目题目描述 Description cc是个超级帅哥，口才又好，rp极高（这句话似乎降rp），又非常的幽默

爱被打了一巴掌/ 2022年08月02日 15:59/ 0 赞/ 90 阅读

相关【基础练习】【堆】codevs1063 合并果子题解

是的我受不了诸城一中的魔鬼DEVCPP了还有魔鬼codeblocks 每次编译都要把六个文件都点一遍删除可执行文件再重新编译= =命令行也各种问题受不了他直接

￡神魔★判官ぃ/ 2022年08月02日 15:53/ 0 赞/ 320 阅读