最小生成树
题目描述
小 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; }