#3600

Maximize Spanning Tree Stability with Upgrades

master · 1720 · lc hard +32 · 39.7% accepted · 70 likes · top 19%

⚑ Minimum Spanning Tree (Kruskal's / Prim's)

Description

A graph has n nodes and edges [ui, vi, si, musti] where si is edge strength. Edges with musti == 1 are mandatory and cannot be upgraded.

You may perform at most k upgrades; each doubles one eligible edge's strength (each edge at most once).

The stability of a spanning tree equals its minimum edge strength.

Return the maximum achievable stability of any valid spanning tree, or -1 if the graph cannot be fully connected.

Note: A spanning tree connects all n nodes with exactly n - 1 edges and no cycles.

Code

1

2

3

class Solution:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:

class Solution:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int: