CommonLounge Archive

HackerRank Week Of Code 31: Spanning Tree Fraction

May 13, 2017

Problem in short: Consider an undirected graph of N nodes, M edges. Each edge is labeled with two integers A, B. Find a spanning tree of this graph which has the maximum possible value for the following expression:

$$ \sum_{edges \in tree} \frac {A_{edge}}{B_{edge}} $$

Constraints: 1 <= N, M <= 10^5

© 2016-2022. All rights reserved.