Fiber Optic Network
Description:
The Problem
The Tutuaçu tribe decided to create a fiber optic network designed to facilitate the communication within the village and the access to information. In order to do that, all houses must be connected directly (using a network branch) or indirectly (using more than one branch). They want to build a network with lowest cost, but they need some help to achieve that. The specialists have gathered all the requirements, including the costs to build each network branch, but they need your help to optimize it.
This is an example of optimization:
Your should create a method to receive their specifications and return the optimized network.
That is...
Given a number of houses n
, a number of network branches k
and a matrix m
with n
rows containing {x,y,z}
where z
is the cost to connect the house x
to the house y
, your method must return a list containing all the branches that must be kept to connect all the houses with lowest cost, e.g: (1,3), (2,3)
, etc.
If there are multiple solutions, return only the first (order by house id).
Examples
* Input:
n = 5, k = 6,
m = |1 2 15|
|1 3 12|
|2 3 6|
|2 4 13|
|2 5 5|
|3 4 6|
fiber_optic_net(n, k, m);
* Return list:
pair<int,int>(1,3)
pair<int,int>(2,3)
pair<int,int>(2,5)
pair<int,int>(3,4)
* Input:
n = 3, k = 3,
m = |1 2 10|
|2 3 10|
|3 1 10|
fiber_optic_net(n, k, m);
* Return list:
pair<int,int>(1,3)
pair<int,int>(2,3)
pair<int,int>(2,5)
pair<int,int>(3,4)
Similar Kata:
Stats:
Created | Dec 7, 2017 |
Published | Dec 7, 2017 |
Warriors Trained | 129 |
Total Skips | 40 |
Total Code Submissions | 47 |
Total Times Completed | 6 |
C++ Completions | 6 |
Total Stars | 8 |
% of votes with a positive feedback rating | 100% of 4 |
Total "Very Satisfied" Votes | 4 |
Total "Somewhat Satisfied" Votes | 0 |
Total "Not Satisfied" Votes | 0 |
Total Rank Assessments | 4 |
Average Assessed Rank | 5 kyu |
Highest Assessed Rank | 4 kyu |
Lowest Assessed Rank | 6 kyu |