3600. 通过升级最大化生成树稳定性

Hard

题目描述

给你一个整数 n，表示编号从 0 到 n - 1 的 n 个节点，以及一个边列表 edges，其中 edges[i] = [ui, vi, si, musti]：

ui 和 vi 表示节点 ui 和 vi 之间的无向边
si 是边的强度
musti 是一个整数（0 或 1）。如果 musti == 1，该边必须包含在生成树中。这些边不能被升级

你还有一个整数 k，表示你可以执行的最大升级次数。每次升级将边的强度翻倍，每条符合条件的边（musti == 0）最多可以升级一次。

生成树的稳定性定义为其中包含的所有边的最小强度分数。

返回任何有效生成树的最大可能稳定性。如果无法连接所有节点，返回 -1。

注意：具有 n 个节点的图的生成树是边的一个子集，它连接所有节点（即图是连通的）而不形成任何环，并且恰好使用 n - 1 条边。

示例 1：

输入：n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1
输出：2
解释：
- 强度为 2 的边 [0,1] 必须包含在生成树中
- 边 [1,2] 是可选的，可以使用一次升级从 3 升级到 6
- 生成树包含这两条边，强度分别为 2 和 6
- 生成树中的最小强度是 2，这是最大可能的稳定性

示例 2：

输入：n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2
输出：6
解释：
- 所有边都是可选的，允许最多 k = 2 次升级
- 将边 [0,1] 从 4 升级到 8，将边 [1,2] 从 3 升级到 6
- 生成树包含这两条边，强度分别为 8 和 6
- 树中的最小强度是 6，这是最大可能的稳定性

示例 3：

输入：n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0
输出：-1
解释：
- 所有边都是强制性的并形成环，违反了生成树的无环性质
- 因此，答案是 -1

约束：

2 <= n <= 10^5
1 <= edges.length <= 10^5
edges[i] = [ui, vi, si, musti]
0 <= ui, vi < n
ui != vi
1 <= si <= 10^5
musti 是 0 或 1
0 <= k <= n
没有重复的边

解题思路

这道题需要求解在有限次升级操作下，生成树的最大稳定性（最小边权的最大值）。

核心思路：

使用二分搜索答案。对于每个候选稳定性值，验证是否可以通过升级构造出满足要求的生成树
验证函数的策略：
- 首先添加所有必须包含的边（musti=1）
- 然后贪心地添加可选边（musti=0），优先选择升级后能达到稳定性要求的边
- 使用并查集维护连通性，确保形成有效生成树

具体实现：

预处理所有可能的稳定性值：原始边权和升级后的边权
二分搜索最大稳定性值
验证函数中：
- 先处理必须边，检查是否形成环
- 再处理可选边，贪心使用升级次数
- 确保最终形成连通的生成树

时间复杂度： O(m log m + log(max_strength) × m α(n))，其中 m 是边数，α 是反阿克曼函数 空间复杂度： O(n + m)

代码实现

class Solution {
public:
    class UnionFind {
    public:
        vector<int> parent, rank;
        int components;
        
        UnionFind(int n) : parent(n), rank(n, 0), components(n) {
            iota(parent.begin(), parent.end(), 0);
        }
        
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        bool unite(int x, int y) {
            int px = find(x), py = find(y);
            if (px == py) return false;
            
            if (rank[px] < rank[py]) swap(px, py);
            parent[py] = px;
            if (rank[px] == rank[py]) rank[px]++;
            components--;
            return true;
        }
    };
    
    bool canAchieveStability(int n, vector<vector<int>>& edges, int k, int target) {
        UnionFind uf(n);
        int upgrades = k;
        
        // Add must edges first
        for (auto& edge : edges) {
            if (edge[3] == 1) {
                if (edge[2] < target) return false;
                if (!uf.unite(edge[0], edge[1])) return false; // cycle
            }
        }
        
        // Sort optional edges by original strength in descending order
        vector<vector<int>> optional;
        for (auto& edge : edges) {
            if (edge[3] == 0) {
                optional.push_back(edge);
            }
        }
        sort(optional.begin(), optional.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] > b[2];
        });
        
        // Add optional edges greedily
        for (auto& edge : optional) {
            if (uf.find(edge[0]) == uf.find(edge[1])) continue;
            
            int strength = edge[2];
            if (strength >= target) {
                uf.unite(edge[0], edge[1]);
            } else if (strength * 2 >= target && upgrades > 0) {
                uf.unite(edge[0], edge[1]);
                upgrades--;
            }
        }
        
        return uf.components == 1;
    }
    
    int maxStability(int n, vector<vector<int>>& edges, int k) {
        set<int> candidates;
        for (auto& edge : edges) {
            candidates.insert(edge[2]);
            candidates.insert(edge[2] * 2);
        }
        
        vector<int> values(candidates.begin(), candidates.end());
        int left = 0, right = values.size() - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canAchieveStability(n, edges, k, values[mid])) {
                result = values[mid];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:
        class UnionFind:
            def __init__(self, n):
                self.parent = list(range(n))
                self.rank = [0] * n
                self.components = n
            
            def find(self, x):
                if self.parent[x] != x:
                    self.parent[x] = self.find(self.parent[x])
                return self.parent[x]
            
            def unite(self, x, y):
                px, py = self.find(x), self.find(y)
                if px == py:
                    return False
                
                if self.rank[px] < self.rank[py]:
                    px, py = py, px
                self.parent[py] = px
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1
                self.components -= 1
                return True
        
        def can_achieve_stability(target):
            uf = UnionFind(n)
            upgrades = k
            
            # Add must edges first
            for u, v, s, must in edges:
                if must == 1:
                    if s < target:
                        return False
                    if not uf.unite(u, v):
                        return False  # cycle
            
            # Sort optional edges by strength descending
            optional = [(u, v, s) for u, v, s, must in edges if must == 0]
            optional.sort(key=lambda x: x[2], reverse=True)
            
            # Add optional edges greedily
            for u, v, s in optional:
                if uf.find(u) == uf.find(v):
                    continue
                
                if s >= target:
                    uf.unite(u, v)
                elif s * 2 >= target and upgrades > 0:
                    uf.unite(u, v)
                    upgrades -= 1
            
            return uf.components == 1
        
        # Get all possible target values
        candidates = set()
        for _, _, s, _ in edges:
            candidates.add(s)
            candidates.add(s * 2)
        
        values = sorted(candidates)
        left, right = 0, len(values) - 1
        result = -1
        
        while left <= right:
            mid = (left + right) // 2
            if can_achieve_stability(values[mid]):
                result = values[mid]
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    public class UnionFind {
        private int[] parent;
        private int[] rank;
        public int Components { get; private set; }
        
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            Components = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        public int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        public bool Unite(int x, int y) {
            int px = Find(x), py = Find(y);
            if (px == py) return false;
            
            if (rank[px] < rank[py]) {
                (px, py) = (py, px);
            }
            parent[py] = px;
            if (rank[px] == rank[py]) rank[px]++;
            Components--;
            return true;
        }
    }
    
    private bool CanAchieveStability(int n, int[][] edges, int k, int target) {
        var uf = new UnionFind(n);
        int upgrades = k;
        
        // Add must edges first
        foreach (var edge in edges) {
            if (edge[3] == 1) {
                if (edge[2] < target) return false;
                if (!uf.Unite(edge[0], edge[1])) return false; // cycle
            }
        }
        
        // Sort optional edges by strength descending
        var optional = new List<int[]>();
        foreach (var edge in edges) {
            if (edge[3] == 0) {
                optional.Add(edge);
            }
        }
        optional.Sort((a, b) => b[2].CompareTo(a[2]));
        
        // Add optional edges greedily
        foreach (var edge in optional) {
            if (uf.Find(edge[0]) == uf.Find(edge[1])) continue;
            
            int strength = edge[2];
            if (strength >= target) {
                uf.Unite(edge[0], edge[1]);
            } else if (strength * 2 >= target && upgrades > 0) {
                uf.Unite(edge[0], edge[1]);
                upgrades--;
            }
        }
        
        return uf.Components == 1;
    }
    
    public int MaxStability(int n, int[][] edges, int k) {
        var candidates = new HashSet<int>();
        foreach (var edge in edges) {
            candidates.Add(edge[2]);
            candidates.Add(edge[2] * 2);
        }
        
        var values = candidates.OrderBy(x => x).ToArray();
        int left = 0, right = values.Length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CanAchieveStability(n, edges, k, values[mid])) {
                result = values[mid];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

var maxStability = function(n, edges, k) {
    function canFormSpanningTree(minStrength, upgrades) {
        const parent = Array.from({length: n}, (_, i) => i);
        
        function find(x) {
            if (parent[x] !== x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        function union(x, y) {
            const px = find(x);
            const py = find(y);
            if (px !== py) {
                parent[px] = py;
                return true;
            }
            return false;
        }
        
        const mustEdges = [];
        const optionalEdges = [];
        
        for (const [u, v, s, must] of edges) {
            if (must === 1) {
                mustEdges.push([u, v, s]);
            } else {
                optionalEdges.push([u, v, s]);
            }
        }
        
        let edgesUsed = 0;
        
        // Add must edges first
        for (const [u, v, s] of mustEdges) {
            if (s < minStrength) return false;
            if (union(u, v)) {
                edgesUsed++;
            } else {
                return false; // cycle with must edges
            }
        }
        
        // Sort optional edges by strength descending
        optionalEdges.sort((a, b) => b[2] - a[2]);
        
        let upgradesUsed = 0;
        
        for (const [u, v, s] of optionalEdges) {
            if (edgesUsed === n - 1) break;
            
            let actualStrength = s;
            let needUpgrade = false;
            
            if (s < minStrength) {
                if (s * 2 >= minStrength && upgradesUsed < upgrades) {
                    actualStrength = s * 2;
                    needUpgrade = true;
                } else {
                    continue;
                }
            }
            
            if (union(u, v)) {
                edgesUsed++;
                if (needUpgrade) {
                    upgradesUsed++;
                }
            }
        }
        
        return edgesUsed === n - 1;
    }
    
    const allStrengths = new Set();
    
    for (const [u, v, s, must] of edges) {
        allStrengths.add(s);
        if (must === 0) {
            allStrengths.add(s * 2);
        }
    }
    
    const strengths = Array.from(allStrengths).sort((a, b) => b - a);
    
    let result = -1;
    
    for (const strength of strengths) {
        if (canFormSpanningTree(strength, k)) {
            result = Math.max(result, strength);
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析