So I’m doing this problem, and I have these steps so far:
- Binary search on the maximum value attainable.
- For each value, sort the list of edges in reverse, tiebreaking by putting the one with the larger numerator first. Then, run Kruskal’s, advancing through the list of edges until an edge with a value less than the target value is it.
The thing is, I don’t know how to process the rest of the edges. Sometimes it’s worth it to select an edge with a lesser value, and sometimes it isn’t. So how would I go about sorting the rest of the edges?
EDIT: Actually, now I don’t even think my second step is correct. Sometimes taking one with the lesser value could be better if its value is large enough.