3600. Maximize Spanning Tree Stability with Upgrades Hard

1/**
2 * [3600] Maximize Spanning Tree Stability with Upgrades
3 *
4 * You are given an integer n, representing n nodes numbered from 0 to n - 1 and a list of edges, where edges[i] = [ui, vi, si, musti]:
5 * 
6 * 	ui and vi indicates an undirected edge between nodes ui and vi.
7 * 	si is the strength of the edge.
8 * 	musti is an integer (0 or 1). If musti == 1, the edge must be included in the spanning tree. These edges cannot be upgraded.
9 * 
10 * You are also given an integer k, the maximum number of upgrades you can perform. Each upgrade doubles the strength of an edge, and each eligible edge (with musti == 0) can be upgraded at most once.
11 * The stability of a spanning tree is defined as the minimum strength score among all edges included in it.
12 * Return the maximum possible stability of any valid spanning tree. If it is impossible to connect all nodes, return -1.
13 * Note: A spanning tree of a graph with n nodes is a subset of the edges that connects all nodes together (i.e. the graph is connected) without forming any cycles, and uses exactly n - 1 edges.
14 *  
15 * <strong class="example">Example 1:
16 * <div class="example-block">
17 * Input: <span class="example-io">n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1</span>
18 * Output: <span class="example-io">2</span>
19 * Explanation:
20 * 
21 * 	Edge [0,1] with strength = 2 must be included in the spanning tree.
22 * 	Edge [1,2] is optional and can be upgraded from 3 to 6 using one upgrade.
23 * 	The resulting spanning tree includes these two edges with strengths 2 and 6.
24 * 	The minimum strength in the spanning tree is 2, which is the maximum possible stability.
25 * </div>
26 * <strong class="example">Example 2:
27 * <div class="example-block">
28 * Input: <span class="example-io">n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2</span>
29 * Output: <span class="example-io">6</span>
30 * Explanation:
31 * 
32 * 	Since all edges are optional and up to k = 2 upgrades are allowed.
33 * 	Upgrade edges [0,1] from 4 to 8 and [1,2] from 3 to 6.
34 * 	The resulting spanning tree includes these two edges with strengths 8 and 6.
35 * 	The minimum strength in the tree is 6, which is the maximum possible stability.
36 * </div>
37 * <strong class="example">Example 3:
38 * <div class="example-block">
39 * Input: <span class="example-io">n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0</span>
40 * Output: <span class="example-io">-1</span>
41 * Explanation:
42 * 
43 * 	All edges are mandatory and form a cycle, which violates the spanning tree property of acyclicity. Thus, the answer is -1.
44 * </div>
45 *  
46 * Constraints:
47 * 
48 * 	2 <= n <= 10^5
49 * 	1 <= edges.length <= 10^5
50 * 	edges[i] = [ui, vi, si, musti]
51 * 	0 <= ui, vi < n
52 * 	ui != vi
53 * 	1 <= si <= 10^5
54 * 	musti is either 0 or 1.
55 * 	0 <= k <= n
56 * 	There are no duplicate edges.
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/maximize-spanning-tree-stability-with-upgrades/
62// discuss: https://leetcode.com/problems/maximize-spanning-tree-stability-with-upgrades/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn max_stability(n: i32, edges: Vec<Vec<i32>>, k: i32) -> i32 {
68        0
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_3600() {
80    }
81}
82