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_{e d g e s \in t r e e} \frac{A_{e d g e}}{B_{e d g e}}

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

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