Connect all the N(<=10^5) cities to make a connected graph in minimum cost. Cost of adding each edge is product of population of the two cities between whom edge is being added. All populations are given in the input.
QUICK EXPLANATION:
Graph formed finally should be a tree. We connect all the other nodes to the node with smallest population which results in minimum cost.
EXPLANATION:
We need to add edges such that all the cities become connected. Connected is defined as âit should be possible from any city to reach any other city by a sequence of edgesâ.
There doesnât exist a graph which is connected and has less than (N-1) edges (which is known as a tree).
So we will be constructing a tree finally with (N-1) edges.
Suppose we create some random tree with (N-1) edges. Now I pick two nodes i and j where Pi and Pj both are not the minimum and remove that edge from there and connect nodes x and j, where Px is minimum.
I have a change of ( Px * Pj ) - ( Pi * Pj ) which is less than zero since Px < Pi.
So, we all nodes will be connected to the node with smallest value.
Pseudo Code:
n=input
value array=input
ans=0
for i=1 to N-1:
ans += value[i]*value[0]
print ans
AUTHORâS AND TESTERâS SOLUTIONS:
Authorâs solution can be found here.
Testerâs solution can be found here.
to avoid integer overflow use â long long â . I had got a WA while using âintâ . and the problem is of
'ad-hoc â category which means you do not require to apply any special algorithm to get it solved .
Complexity of Kruskalâs is O(ElogV), while of this algorithm is linear. I guess it might result in TLE. Morever this algorithm is very easy to implement unlike Kruskal.
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int T,N;
cin>>T;
while(Tâ)
{
cin>>N;
long long int arr[N];
for(long long int i=0;i<N;i++)
{
cin>>arr[i];
}
sort(arr,arr+N);
long long int sum=0;
for(long long int i=1;i<N;i++)
{
sum+=arr[i]*arr[0];
}
cout<<sum<<endl;
}
}