Beta

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:

fiber-optic-network-example

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)
  
Algorithms
Lists
Graph Theory

Stats:

CreatedDec 7, 2017
PublishedDec 7, 2017
Warriors Trained129
Total Skips40
Total Code Submissions47
Total Times Completed6
C++ Completions6
Total Stars8
% of votes with a positive feedback rating100% of 4
Total "Very Satisfied" Votes4
Total "Somewhat Satisfied" Votes0
Total "Not Satisfied" Votes0
Total Rank Assessments4
Average Assessed Rank
5 kyu
Highest Assessed Rank
4 kyu
Lowest Assessed Rank
6 kyu
Ad
Contributors
  • drexduarte Avatar
  • siebenschlaefer Avatar
  • kazk Avatar
  • Voile Avatar
Ad