链接:https://www.nowcoder.com/acm/contest/204/D
来源:牛客网
题目描述
小 A 有一张 n 个点的带权无向图,这张无向图非常特别,首先第 i 个点有一个点权 ai,之后这张无向图是一张完全图,且边 (u,v) 的权值为 au+av
现在小 A 想找一个这张图的边权之和最小的生成树,需要你来帮帮他
输入描述:
第一行一个正整数 n
第二行 n 个整数 a1,a2…an
输出描述:
输出边权和最小的生成树的边权之和
示例1
输入
复制
3
1 2 3
输出
复制
7
备注:
1≤ n≤ 105
0≤ ai≤ 109

假的最小生成树…
因为是完全图,也就是每个点到其他n-1个点都有边,那直接全部加起来,再加上n-2即可

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
int n;
const int N=1e5+50;
long long a[N];
int main(void){
   
    scanf("%d",&n);
    long long ans=0;
    for(int i=0;i<n;i++){
   
        scanf("%lld",&a[i]);
        ans+=a[i];
    }
    sort(a,a+n);
    ans+=a[0]*(n-2);
    printf("%lld\n",ans);
    return 0;
}