【2018ACM山东省赛 - C】Cities（最小生成树变形优化，贪心思维）

题干：

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连起来，得到的一定更优。由此归纳，每个边都可以转换成和x号点连接的边，得到最优解。证毕。

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（最小生成树变形优化，贪心思维）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。