Medium

题目描述

给定两个整数 n 和 threshold，以及一个由 n 个节点（编号从 0 到 n-1）组成的有向加权图。图由二维整数数组 edges 表示，其中 edges[i] = [Ai, Bi, Wi] 表示从节点 Ai 到节点 Bi 有一条权重为 Wi 的边。

你需要从图中移除一些边（可能不移除），使其满足以下条件：

  • 节点 0 必须能从所有其他节点到达
  • 结果图中的最大边权重最小化
  • 每个节点最多有 threshold 条出边

返回移除必要边后最大边权重的最小可能值。如果无法满足所有条件，返回 -1。

示例 1：

输入：n = 5, edges = [[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]], threshold = 2
输出：1
解释：移除边 2 -> 0。剩余边中的最大权重为 1。

示例 2：

输入：n = 5, edges = [[0,1,1],[0,2,2],[0,3,1],[0,4,1],[1,2,1],[1,4,1]], threshold = 1
输出：-1
解释：无法从节点 2 到达节点 0。

示例 3：

输入：n = 5, edges = [[1,2,1],[1,3,3],[1,4,5],[2,3,2],[3,4,2],[4,0,1]], threshold = 1
输出：2
解释：移除边 1 -> 3 和 1 -> 4。剩余边中的最大权重为 2。

提示：

  • 2 <= n <= 10^5
  • 1 <= threshold <= n - 1
  • 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
  • edges[i].length == 3
  • 0 <= Ai, Bi < n
  • Ai != Bi
  • 1 <= Wi <= 10^6

解题思路

这是一个图论问题，需要在满足连通性和度数约束的前提下最小化最大边权重。

核心思路

  1. 转换问题：根据提示，我们需要反转图的边方向。原问题要求"节点0必须能从所有其他节点到达"，反转边后变成"所有节点必须能从节点0到达"。

  2. 二分答案：对最大边权重进行二分搜索。对于每个候选值 mid，我们只保留权重 ≤ mid 的边，然后检查是否能满足所有条件。

  3. 验证函数：给定最大边权重限制 mid，需要验证：

    • 每个节点的出度不超过 threshold
    • 从节点0出发能到达所有其他节点

算法流程

  1. 收集所有边权重并排序，用于二分搜索的边界
  2. 对边权重进行二分搜索
  3. 对于每个候选答案，构建只包含权重不超过该值的边的图
  4. 对每个节点，如果出度超过 threshold，则贪心地保留权重最小的 threshold 条边
  5. 使用BFS/DFS从节点0检查连通性

关键优化

  • 反转边后，问题变为从源点0到达所有节点的最短路径问题
  • 贪心策略：当某个节点出度超限时，优先保留权重小的边
  • 二分搜索大大减少了需要验证的候选答案数量

代码实现

class Solution {
public:
    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
        // 反转边并收集权重
        vector<vector<pair<int, int>>> graph(n);
        vector<int> weights;
        
        for (auto& edge : edges) {
            graph[edge[1]].push_back({edge[0], edge[2]});
            weights.push_back(edge[2]);
        }
        
        sort(weights.begin(), weights.end());
        weights.erase(unique(weights.begin(), weights.end()), weights.end());
        
        int left = 0, right = weights.size() - 1, result = -1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int maxWeight = weights[mid];
            
            if (canReachAll(graph, n, threshold, maxWeight)) {
                result = maxWeight;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
private:
    bool canReachAll(vector<vector<pair<int, int>>>& graph, int n, int threshold, int maxWeight) {
        vector<vector<pair<int, int>>> filteredGraph(n);
        
        // 构建过滤后的图
        for (int i = 0; i < n; i++) {
            vector<pair<int, int>> validEdges;
            for (auto& [to, weight] : graph[i]) {
                if (weight <= maxWeight) {
                    validEdges.push_back({to, weight});
                }
            }
            
            // 如果出度超过threshold，保留权重最小的edges
            if (validEdges.size() > threshold) {
                sort(validEdges.begin(), validEdges.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
                    return a.second < b.second;
                });
                validEdges.resize(threshold);
            }
            
            filteredGraph[i] = validEdges;
        }
        
        // BFS检查从节点0是否能到达所有节点
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(0);
        visited[0] = true;
        int reachable = 1;
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            
            for (auto& [next, weight] : filteredGraph[curr]) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.push(next);
                    reachable++;
                }
            }
        }
        
        return reachable == n;
    }
};

class Solution:
    def minMaxWeight(self, n: int, edges: List[List[int]], threshold: int) -> int:
        # 反转边并收集权重
        graph = [[] for _ in range(n)]
        weights = set()
        
        for a, b, w in edges:
            graph[b].append((a, w))
            weights.add(w)
        
        weights = sorted(weights)
        
        def canReachAll(maxWeight):
            # 构建过滤后的图
            filteredGraph = [[] for _ in range(n)]
            
            for i in range(n):
                validEdges = []
                for to, weight in graph[i]:
                    if weight <= maxWeight:
                        validEdges.append((to, weight))
                
                # 如果出度超过threshold，保留权重最小的边
                if len(validEdges) > threshold:
                    validEdges.sort(key=lambda x: x[1])
                    validEdges = validEdges[:threshold]
                
                filteredGraph[i] = validEdges
            
            # BFS检查从节点0是否能到达所有节点
            visited = [False] * n
            queue = [0]
            visited[0] = True
            reachable = 1
            
            while queue:
                curr = queue.pop(0)
                for next_node, weight in filteredGraph[curr]:
                    if not visited[next_node]:
                        visited[next_node] = True
                        queue.append(next_node)
                        reachable += 1
            
            return reachable == n
        
        left, right = 0, len(weights) - 1
        result = -1
        
        while left <= right:
            mid = (left + right) // 2
            maxWeight = weights[mid]
            
            if canReachAll(maxWeight):
                result = maxWeight
                right = mid - 1
            else:
                left = mid + 1
        
        return result

public class Solution {
    public int MinMaxWeight(int n, int[][] edges, int threshold) {
        // 反转边并收集权重
        var graph = new List<List<(int, int)>>();
        for (int i = 0; i < n; i++) {
            graph.Add(new List<(int, int)>());
        }
        
        var weightSet = new HashSet<int>();
        
        foreach (var edge in edges) {
            graph[edge[1]].Add((edge[0], edge[2]));
            weightSet.Add(edge[2]);
        }
        
        var weights = weightSet.ToArray();
        Array.Sort(weights);
        
        int left = 0, right = weights.Length - 1, result = -1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int maxWeight = weights[mid];
            
            if (CanReachAll(graph, n, threshold, maxWeight)) {
                result = maxWeight;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
    private bool CanReachAll(List<List<(int, int)>> graph, int n, int threshold, int maxWeight) {
        var filteredGraph = new List<List<(int, int)>>();
        for (int i = 0; i < n; i++) {
            filteredGraph.Add(new List<(int, int)>());
        }
        
        // 构建过滤后的图
        for (int i = 0; i < n; i++) {
            var validEdges = new List<(int, int)>();
            foreach (var (to, weight) in graph[i]) {
                if (weight <= maxWeight) {
                    validEdges.Add((to, weight));
                }
            }
            
            // 如果出度超过threshold，保留权重最小的边
            if (validEdges.Count > threshold) {
                validEdges.Sort((a, b) => a.Item2.CompareTo(b.Item2));
                filteredGraph[i] = validEdges.GetRange(0, threshold);
            } else {
                filteredGraph[i] = validEdges;
            }
        }
        
        // BFS检查从节点0是否能到达所有节点
        var visited = new bool[n];
        var queue = new Queue<int>();
        queue.Enqueue(0);
        visited[0] = true;
        int reachable = 1;
        
        while (queue.Count > 0) {
            int curr = queue.Dequeue();
            foreach (var (next, weight) in filteredGraph[curr]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.Enqueue(next);
                    reachable++;
                }
            }
        }
        
        return reachable == n;
    }
}

var minMaxWeight = function(n, edges, threshold) {
    const weights = [...new Set(edges.map(e => e[2]))].sort((a, b) => a - b);
    
    function canReach(maxWeight) {
        const validEdges = edges.filter(e => e[2] <= maxWeight);
        const graph = Array(n).fill().map(() => []);
        
        for (const [u, v, w] of validEdges) {
            graph[u].push([v, w]);
        }
        
        for (let i = 0; i < n; i++) {
            graph[i].sort((a, b) => a[1] - b[1]);
            if (graph[i].length > threshold) {
                graph[i] = graph[i].slice(0, threshold);
            }
        }
        
        const visited = new Set();
        const queue = [0];
        visited.add(0);
        
        while (queue.length > 0) {
            const node = queue.shift();
            for (const [neighbor] of graph[node]) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
        
        return visited.size === n;
    }
    
    let left = 0, right = weights.length - 1;
    let result = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canReach(weights[mid])) {
            result = weights[mid];
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(E log W × (E log threshold + V + E))，其中 E 是边数，W 是不同权重数，V 是节点数。二分搜索 O(log W)，每次验证需要排序 O(E log threshold) 和 BFS O(V + E)
空间复杂度O(V + E)，用于存储图结构和 BFS 访问数组