链接: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;
}