题解 | #最小生成树#

链接

解题思路如下：

由于输入给的是各点的点权而不是边权，要得要最小生成树（题目要求的输出是边权） 找出点权最小的点A，让其与（n-1）各点相连，在这里A的点权被运用了（n-1）次，而其余各点的点权被使用一次。就拿题目输入的来说，最后得到的输出是（1+2）+（1+3）得到的，实际上就是1*（3-1）(ps:这里的3是n)+（1+2+3-1）(这里的1+2+3是n个点的点权之和)，则最后的输出答案就是min*(n-1)+sum-min

#include<stdlib.h>
int main(){
    long long  n;
    scanf("%lld",&n);
    long long a[100000];
    long long min=1e9;
    long long sum=0,i;
    for(i=0;i<n;i++){
        scanf("%lld",&a[i]);
        sum+=a[i];
        if(a[i]<min){
            min=a[i];
        }
    } 
    printf("%lld\n",sum-min+min*(n-1));
    return 0;
}