遇到一个求边权和的问题，求解答。
现在有 n 个点 (1<=n<=1000)，每个点都有一个值称为点权 ai(ai 为偶数,1<=ai<=1000)，现在可以将任意两个点相连，连起来以后这条边也有一个值称为边权，这个边的边权为这两个点的点权之和的一半。现在需要你添加 n-1 条边，问将这 n 个点连通以后 ( 连通是指任意两个点都能互相到达 ) 的最大的边权和是多少 ? 输入点的数量 n；和 n 个数，表示点权的值,输出最大的边权和.
展开
收起
1
条回答
写回答
写回答
-
根据题意可知，最终需要将 n 个点连通并达到最大边权，而边权为两个点的点权之和 的一半，所以一个点加入连通图的最大边权就是和点权最大的点连通。因此想要得到最大边权和，只要所有点都与点权最大的点相连即可。实现过程中，首先求出最大的点权，然后计算出其他点与这个权值最大的点的边权之和即可。 则输入：5 [2,4,6,8,10]
输出：30。2021-12-23 18:16:09赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
