最小生成树

最小生成树

题目描述

小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 ai，之后这张无向图是一张完全图，且边 (u,v) 的权值为 au+av
现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他

可以用prim算法跑出来最小生成树，但是仔细想可以用贪心的思路：

将点权从小到大排序，a[1]和其他各点连接就是最小生成树

#pragma GCC optimize (3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll a[100005];
int main(){
    js;
    ll n;
    cin>>n;
    ll sum=0;
    ll Min=1e18;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        Min=min(Min,a[i]);
    } 
    cout<<(n-1)*Min+sum-Min;


}