Show problems as
Classic problem #3600HardBinary SearchGreedyUnion-FindGraph TheoryMinimum Spanning Tree

Maximize Spanning Tree Stability with Upgrades

Real-world version: Strongest Weakest Link in the Mesh
Tracked in this browser only
Read Maximize Spanning Tree Stability with Upgrades on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A mesh joins n relay sites numbered 0 through n - 1. Each entry edges[i] = [u, v, s, must] describes a possible two-way link between site u and site v whose signal strength is s. When must is 1 the link is already laid and has to stay; when it is 0 the link is optional. No two entries describe the same pair of sites.

The operator installs a set of links so that every site is reachable from every other and no loop is formed, which means exactly n - 1 links. Before doing so the operator may pick at most k of the optional links and double their signal strength. A link that has to stay can never be doubled.

The stability of the finished mesh is the strength of its weakest installed link. Return the largest stability achievable, or -1 if the links that have to stay already form a loop or no choice connects every site.

Examples

Example 1

Input
n = 3, edges = [[0, 1, 4, 0], [1, 2, 3, 0], [0, 2, 2, 0]], k = 1
Output
4

Installing the links of strength 4 and 3 connects all three sites, and doubling the one of strength 3 makes it 6, so the weakest installed link has strength 4.

Example 2

Input
n = 3, edges = [[0, 1, 5, 1], [1, 2, 5, 1], [0, 2, 5, 1]], k = 2
Output
-1

All three links have to stay, and together they close a loop around the three sites, which the mesh is not allowed to contain.

Example 3

Input
n = 3, edges = [[0, 1, 7, 0]], k = 2
Output
-1

Site 2 appears in no link at all, so no set of links reaches every site and the answer is -1.

Constraints

  • 2 <= n <= 10^5
  • 1 <= edges.length <= 10^5
  • edges[i].length == 4
  • 0 <= edges[i][0] <= 99999
  • 0 <= edges[i][1] <= 99999
  • 1 <= edges[i][2] <= 10^5
  • 0 <= edges[i][3] <= 1
  • 0 <= k <= 10^5
  • A link never joins a site to itself, and no pair of sites appears twice

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_weakest_link(n: int, edges: list[list[int]], k: int) -> int:
Java
public int bestWeakestLink(int n, int[][] edges, int k)

More on the same topics