【阿里云在线编程】 44.最大边权和

Myth丶恋晨 2021-06-10 20:38 351阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

1.  边权是两个点的权值相加除以2，n个点连通需要n-1条边，想让边权和最大，那就让每条边都达到最大就好了
2.  要想让每条边的边权都最大，其实让除最大权值的点都连接到权值最大的点就好了  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]

### code ###

package solution44;
    
    class Solution { 
        public int solution(int n,int[] nums) { 
            int max = Integer.MIN_VALUE;
            int res = 0;
            for(int i = 0; i < n; i++){ 
                if(nums[i] > max) { 
                    max = nums[i];
                }
                res += nums[i];
            }
            res = res + max * ( n - 2 );
            res /= 2;
            return res;
        }
    }

[Link 1]: https://developer.aliyun.com/coding/44
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/48868f8ed2864917b6c0a7efab91941a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/e7f31a4434184b35b3805319e8365070.png