Maximize Spanning Tree Stability With Upgrades · Interview Problem

Back to problems

Leetcode

maximize-spanning-tree-stability-with-upgrades

Medium

Graphs

Union Find

Minimum Spanning Tree

Maximize Spanning Tree Stability With Upgrades

Find the maximum possible stability of a spanning tree after performing a limited number of edge upgrades.

Acceptance 33%

Start Practice

Problem Statement

Core description from the backend problem record.

Description

Given a weighted undirected graph and a number of upgrades available that can increase the weight of certain edges, the goal is to maximize the stability of the spanning tree constructed from this graph by upgrading some edges. Stability is measured by a certain function defined over the spanning tree edges' weights after upgrades. The problem requires selecting edges to upgrade before building the maximum spanning tree to achieve maximum stability.

Input Format

An integer n, the number of nodes in the graph (nodes labeled 1 to n).
An array edges where each element is a triplet (u, v, w) representing an undirected edge between nodes u and v with weight w.
An integer k representing the number of upgrades allowed.
An integer upgradeValue representing how much weight can be increased by upgrading an edge.

Output Format

Return an integer representing the maximum spanning tree stability possible after performing at most k upgrades optimally.

Constraints

1 <= n <= 10^4
1 <= number of edges <= 2*10^4
1 <= w <= 10^5 for each edge
0 <= k <= number of edges
upgradeValue >= 0

Loading Preptin

Description

Input Format

Output Format

Constraints