題干：

Problem Description

There are nnn cities in Byteland, and the ithi_{th}ith? city has a value aia_iai?. The cost of building a bidirectional road between two cities is the sum of their values. Please calculate the minimum cost of connecting these cities, which means any two cities can reach each other.

Input

The first line is an integer TTT(T≤105T\leq10^5T≤105), representing the number of test cases.
For each test case, the first line is an integer nnn(n≤105n\leq10^5n≤105), representing the number of cities, the second line are n positive integers aia_iai?(ai≤105a_i\leq10^5ai?≤105), representing their values.

Output

The first line is an integer TTT(T≤105T\leq10^5T≤105), representing the number of test cases.
For each test case, the first line is an integer nnn(n≤105n\leq10^5n≤105), representing the number of cities, the second line are n positive integers aia_iai?(ai≤105a_i\leq10^5ai?≤105), representing their values.

Sample Input

2 4 1 2 3 4 1 1

Sample Output

12 0

題目大意：

? ?給定n(<=1e5)個點，告訴你每個點的點權，并告訴你一條邊連接兩個點u和v的話，邊權是a[u]+a[v]，求最小生成樹。

解題報告：

? ?直接貪心，每個點都和最小的點連起來就行了。證明如下：假設點權最小的點是x，最終答案是這一棵樹G，那么對于某一條邊e的兩個點u，v，考慮去掉這條邊之后，一定有一個和x連通，一個和x不連通，假設分別為u和v，那么我們將v和x連起來，得到的一定更優(yōu)。由此歸納，每個邊都可以轉換成和x號點連接的邊，得到最優(yōu)解。證畢。

AC代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<vector> #define mod (1000000007) #define pi acos(-1.0) using namespace std; typedef long long ll; int a[1001000]; int main() {int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);} sort(a,a+n);ll sum=0;for(int i=1;i<n;i++) {sum+=a[i];}sum+=a[0]*1ll*(n-1);printf("%lld\n",sum);}return 0; }

?

總結

以上是生活随笔為你收集整理的【2018ACM山东省赛 - C】Cities（最小生成树变形优化，贪心思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。