连接表示为数组的加权节点的最小成本-yiteyi-C++库

给定一个由N个元素（节点）组成的数组，其中每个元素都是该节点的权重。连接两个节点将以其权重的乘积为代价。必须将每个节点与其他节点连接（直接或间接）。输出所需的最低成本。 例如：

null

Input : a[] = {6, 2, 1, 5}Output :  13Explanation : Here, we connect the nodes as follows:connect a[0] and a[2], cost = 6*1 = 6,connect a[2] and a[1], cost = 1*2 = 2,connect a[2] and a[3], cost = 1*5 = 5.every node is reachable from every other node:Total cost = 6+2+5 = 13.Input  : a[] = {5, 10}Output : 50Explanation : connections:connect a[0] and a[1], cost = 5*10 = 50,Minimum cost = 50.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们需要做一些观察，我们必须做一个N-1边的连通图。由于输出是两个数的乘积之和，我们必须最小化该和方程中每项的乘积。我们怎么做？显然，选择阵列中的最小元素，并将其相互连接。通过这种方式，我们可以从特定节点到达其他每个节点。设，最小元素=a[i]，（设其索引为0） 最低成本 所以，答案是 最小元素与除最小元素外的所有元素之和的乘积。

C++

                         // cpp code for Minimum Cost Required to connect weighted nodes                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         int                                     minimum_cost(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 int                                     mn = INT_MAX;                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // To find the minimum element                       
                                                 mn = min(a[i], mn);                       
           
                                                 // sum of all the elements                       
                                                 sum += a[i];                       
                                                 }                       
           
                                                 return                                     mn * (sum - mn);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { 4, 3, 2, 5 };                       
                                                 int                                     n =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
                                                 cout << minimum_cost(a, n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java code for Minimum Cost Required to                       
                         // connect weighted nodes                       
           
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     minimum_cost(                                     int                                     a[],                                     int                                     n)                       
                                                 {                       
                                   
                                                 int                                     mn = Integer.MAX_VALUE;                       
                                                 int                                     sum =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
           
                                                 // To find the minimum element                       
                                                 mn = Math.min(a[i], mn);                       
           
                                                 // sum of all the elements                       
                                                 sum += a[i];                       
                                                 }                       
           
                                                 return                                     mn * (sum - mn);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     a[] = {                                     4                                     ,                                     3                                     ,                                     2                                     ,                                     5                                     };                       
                                                 int                                     n = a.length;                       
                                   
                                                 System.out.println(minimum_cost(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

Python 3

                         # Python 3 code for Minimum Cost                       
                         # Required to connect weighted nodes                       
                         import                                     sys                       
           
                         def                                     minimum_cost(a, n):                       
           
                                                 mn                                     =                                     sys.maxsize                       
                                                 sum                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 # To find the minimum element                       
                                                 mn                                     =                                     min                                     (a[i], mn)                       
           
                                                 # sum of all the elements                       
                                                 sum                                     +                                     =                                     a[i]                       
           
                                                 return                                     mn                                     *                                     (                                     sum                                     -                                     mn)                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                   
                                                 a                                     =                                     [                                     4                                     ,                                     3                                     ,                                     2                                     ,                                     5                                     ]                       
                                                 n                                     =                                     len                                     (a)                       
                                                 print                                     (minimum_cost(a, n))                       
           
                         # This code is contributed                       
                         # by ChitraNayal                       

C#

                         // C# code for Minimum Cost Required                       
                         // to connect weighted nodes                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Function to calculate minimum cost                       
                                                 static                                     int                                     minimum_cost(                                     int                                     []a,                                     int                                     n)                       
                                                 {                       
                                   
                                                 int                                     mn =                                     int                                     .MaxValue;                       
                                                 int                                     sum = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
           
                                                 // To find the minimum element                       
                                                 mn = Math.Min(a[i], mn);                       
           
                                                 // sum of all the elements                       
                                                 sum += a[i];                       
                                                 }                       
           
                                                 return                                     mn * (sum - mn);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []a = {4, 3, 2, 5};                       
                                                 int                                     n = a.Length;                       
                                   
                                                 Console.WriteLine(minimum_cost(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP code for Minimum Cost Required                       
                         // to connect weighted nodes                       
                         function                                     minimum_cost(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                                 $mn                                     = PHP_INT_MAX;                       
                                                 $sum                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
           
                                                 // To find the minimum element                       
                                                 $mn                                     = min(                                     $a                                     [                                     $i                                     ],                                     $mn                                     );                       
           
                                                 // sum of all the elements                       
                                                 $sum                                     +=                                     $a                                     [                                     $i                                     ];                       
                                                 }                       
           
                                                 return                                     $mn                                     * (                                     $sum                                     -                                     $mn                                     );                       
                         }                       
           
                         // Driver code                       
                         $a                                     =                                     array                                     ( 4, 3, 2, 5 );                       
                         $n                                     = sizeof(                                     $a                                     );                       
                         echo                                     minimum_cost(                                     $a                                     ,                                     $n                                     ),                                     ""                                     ;                       
           
                         // This code is contributed                       
                         // by Kiit_Tush                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript code for Minimum Cost Required                       
                                                 // to connect weighted nodes                       
                                   
                                                 // Function to calculate minimum cost                       
                                                 function                                     minimum_cost(a, n)                       
                                                 {                       
                                   
                                                 let mn = Number.MAX_VALUE;                       
                                                 let sum = 0;                       
                                   
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // To find the minimum element                       
                                                 mn = Math.min(a[i], mn);                       
                                   
                                                 // sum of all the elements                       
                                                 sum += a[i];                       
                                                 }                       
                                   
                                                 return                                     mn * (sum - mn);                       
                                                 }                       
                                   
                                                 let a = [4, 3, 2, 5];                       
                                                 let n = a.length;                       
           
                                                 document.write(minimum_cost(a, n));                       
                                   
                         </script>                       

输出：

时间复杂性： O（n）。本文由 哈莎·莫加利 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章