【“浪潮杯”第九届山东省ACM大学生程序设计竞赛重现赛】C 题 ------ Cities

心已赠人 2022-05-24 05:57 146阅读 0赞

## 题目描述 ##

[原题传送门 - 牛客网][-]

时间限制：C/C++ 1秒，其他语言2秒  
空间限制：C/C++ 65536K，其他语言131072K  
64bit IO Format: %lld

**题目描述：**

There are **n** cities in Byteland, and the **i** city has a value **a** . 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.

**输入描述：**

The first line is an integer T（T<= 1e5）  
representing the number of test cases.

For each test case, the first line is an integer n(n <= 1e5), representing the number of cities, the  
second line are **n** positive integers **a** (a <= 1e5),  
representing their values.

**输出描述：**

For each test case, output an integer, which is the  
minimum cost of connecting these cities.

**示例1**

输入

2
    4
    1 2 3 4
    1
    1

输出

12
    0

## 题目分析 ##

我做这道题目是在比赛后做的，因为比赛的时候时间上安排不过来，所以报名了比赛但是水了 @@

看了下牛客上边的榜单，显然这道题目就是签到题嘛，阿西吧

认真读了下题目，发现题目描述还蛮简单的，我这英语渣都能直接读懂，\_

一开始感觉这道题目就是一道图论，求最小生成树。

二话不说就开始打开Code:Blocks，阿西吧

看着软件打开，我心里构思了下这道题目的解法，我的天，这什么玩意儿的最小生成树，根本就没有好吧，

想了下，就一个简单的配对求和，求最值

**真正的思路：\_**

要想花费最小，其实就是每条边都要最小，我们从定义出发，边的大小取决于点的value，那么，value越小就意味着边最小，对于当前点来说，本身value一定，那么找图中value最小的点进行配对，则花费最小。

坑点在于当点只有一个的时候，花费为0（样例已经给出了这种情况，签到嘛）

## AC代码 ##

#include <bits/stdc++.h>
    using namespace std;
    int main(){
        int t;
        cin>>t;
        while(t--){
            int n;
            cin>>n;
            long long res = 0;
            int minVal = 99999999;   //此处设置为大于a的上限即可
            for(int i=0;i<n;i++){
                int temp;
                cin>>temp;
                if(temp < minVal){
                    minVal = temp;
                }
                res += temp;
            }
            if(n == 1){
                cout<<0<<endl;
            } else{
                cout<<res + (n-2)*minVal<<endl;
            }
        }
        return 0;
    }

**注：**

如有错误，欢迎dalao指正 \_

[-]: https://www.nowcoder.com/acm/contest/123/C