问题2413--连通最小乘积

2413: 连通最小乘积

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交
解决: 12提交量: 29统计

题目描述

一个图上有n个点，点的编号为1,2,...,n。i号点有一个权值Ai。对于一对点(i,j),i≠j,1≤i,j≤n，连通i和j的代价为Ai×Aj。

咸鱼学长想请你以最小的总代价使这个图连通，你能帮帮他吗？

注意，图中的边是无向的，你不能选择重边。即你不能选择连通(i,j)后再次选择连通(j,i)。

输入

第一行输入一个整数n，2≤n≤2×105。
第二行输入n个整数ai，依次代表1号点到n号点的权值。满足−103≤ai≤103

输出

输出一行一个整数，代表答案。

样例输入 Copy 

6
-1 -2 -3 4 5 6

样例输出 Copy 

-90

来源/分类

计算机学院2023级ACM集训队选拔赛（3） 
提交