正规代运营公司排名,网站seo文章该怎么写,网站模版二次开发跟手工制作区别,公司宣传册设计与制作图片问题 D: 最小生成树II
时间限制: 1 Sec 内存限制: 128 MB 提交: 89 解决: 44 [提交] [状态] [讨论版] [命题人:admin] 题目描述
小A有一张n个点的带权无向图#xff0c;这张无向图非常特别#xff0c;首先第i个点有一个点权ai#xff0c;之后这张无向图是一张完全图这张无向图非常特别首先第i个点有一个点权ai之后这张无向图是一张完全图且边(u,v)的权值为auav。现在小A想找一个这张图的边权之和最小的生成树需要你来帮帮他。 输入
第一行一个正整数n 第二行n个整数a1,a2…an 1≤n≤105 0≤ai≤109 输出
输出边权和最小的生成树的边权之和 样例输入
3
1 2 3样例输出
7方法因为两点之间的边一定是等于这两点的权相加所以若要生成权和最小的一棵树则每条边的权要尽可能的小因此此题只需要找到权最小的点并以这点为起点与每一个其他点两两相连这样构成的树权和一定最小。
AC代码
#include cstdio
#include iostream
#include algorithm
#include cmath
#include cstdlib
#include cstring
#include map
#include stack
#include queue
#include vector
#include bitset
#include set
#include utility
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e5 5;
const ll mod 1e97;
int main()
{//freopen(in.txt, r, stdin);//freopen(out.txt, w, stdout);ios::sync_with_stdio(0),cin.tie(0);ll n;cinn;ll nape0;ll a;ll minnmod;for(ll i1;in;i) {cina;napea;minnmin(minn,a);}napeminn*(n-2);if(n1)cout0endl;elsecoutnapeendl;return 0;
}
相关文章：
