雲計算

在线编程-44最大边权和

题目

现在有n个点(1<=n<=1000),每个点都有一个值称为点权ai(ai为偶数,1<=ai<=1000),现在可以将任意两个点相连,连起来以后这条边也有一个值称为边权,这个边的边权为这两个点的点权之和的一半。现在需要你添加n-1条边,问将这n个点连通以后(连通是指任意两个点都能互相到达)的最大的边权和是多少。
输入点的数量n;和n个数,表示点权的值
输出最大的边权和

分析

拿到这个题目,个人理解,总共有以下要点:

  • 所有点全部连通:意味着所有数字要使用一遍
  • 添加n-1条边:控制上限
  • 边权为这两个点的点权之和的一半:意味着两个点数值越大,则边权越大;

通过以上,可以得出,所有点均和最大点做匹配,则能拿到最大的边权和

而1<=n<=1000,则应该分类讨论

  • n=1:无边,因此为0
  • n=2:两数之和/2
  • 其他:sum = (max*(n-2)+n个点之和)/2

源码

详细源码见 https://code.aliyun.com/xinYe/aliProgrammaCode.git

Leave a Reply

Your email address will not be published. Required fields are marked *