2025-12-27：恢复网络路径。用go语言，给定一个有向无环图，节点编号为 0 到 n-1，边集合由长度为 m 的数组 ed

福大大架构师每日一题

发布于 2025-12-30 19:39:16

1570

2025-12-27：恢复网络路径。用go语言，给定一个有向无环图，节点编号为 0 到 n-1，边集合由长度为 m 的数组 edges 表示。每个 edges[i] = [u_i, v_i, cost_i] 表示从节点 u_i 指向节点 v_i 的有向边，且这条边的恢复成本为 cost_i。

另外，每个节点有在线状态，使用布尔数组 online 描述，其中 online[i] = true 表示节点 i 当前在线（注意节点 0 和 n-1 保证始终在线）。

考虑从 0 到 n-1 的一条路径。若该路径满足以下两点，则称其可行：

• 路径上除起点和终点外的所有中间节点均为在线状态；
• 路径上所有边的恢复成本之和不超过给定上限 k。

对于任意一条可行路径，其得分定义为该路径上边成本的最小值（即路径的瓶颈边成本）。问题要求返回所有可行路径中得分的最大值；若不存在任何可行路径，则返回 -1。

n == online.length。

2 <= n <= 5 * 10000。

0 <= m == edges.length <= min(105, n * (n - 1) / 2)。

edges[i] = [ui, vi, costi]。

0 <= ui, vi < n。

ui != vi。

0 <= costi <= 1000000000。

0 <= k <= 5 * 10000000000000。

online[i] 是 true 或 false，且 online[0] 和 online[n - 1] 均为 true。

给定的图是一个有向无环图。

输入: edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10。

输出: 3。

解释:

图中有两条从节点 0 到节点 3 的可能路线：

路径 0 → 1 → 3

总成本 = 5 + 10 = 15，超过了 k (15 > 10)，因此此路径无效。

路径 0 → 2 → 3

总成本 = 3 + 4 = 7 <= k，因此此路径有效。

此路径上的最小边成本为 min(3, 4) = 3。

没有其他有效路径。因此，所有有效路径分数中的最大值为 3。

题目来自力扣3620。

🔍 解题步骤详解

1. 图的构建与预处理
- • 首先，根据输入的边集 edges 和节点在线状态 online，构建邻接表 g 来表示图。这里有一个关键过滤：只保留起点和终点都在线的边。这意味着，如果一条边的起点或终点节点不在线（除0和n-1外），这条边将不会被加入图中。
- • 同时，计算每个节点的入度 deg，并记录从节点0出发的边的最大成本 maxWt，为后续的二分搜索确定上界。这一步主要是为了构建一个仅包含有效边的图结构。
2. 清理无效节点和边
- • 由于图是有向无环图，可能存在一些节点无法从节点0到达，或者无法到达节点n-1。为了避免这些节点干扰后续计算，代码进行了一次“拓扑清理”。
- • 具体做法是：将所有入度为0且不是节点0的节点加入队列（因为这些节点不可能是从0出发能到达的）。然后进行类似拓扑排序的过程，将这些节点及其出边从图中移除（通过减少其邻居节点的入度来实现）。这一步确保了后续动态规划只处理那些可能位于从0到n-1路径上的节点。
3. 二分搜索确定瓶颈值
- • 问题的核心是找到最大的瓶颈值 L，使得存在一条路径，其上的每条边成本都至少为 L，同时路径总成本不超过 k，并且路径上的中间节点都在线。
- • 代码使用二分搜索来寻找这个最佳的 L。搜索范围的下界是0，上界是步骤1中记录的 maxWt。
- • 对于每一个猜测的候选值 lower，代码会判断是否存在满足条件的路径。这个过程将原问题转化为了一个判定性问题 。
4. 判定性问题的解决：带限制的最短路径
- • 对于每个候选值 lower，需要在图上进行一次动态规划（实际上计算的是最短路径，但目的用于判定）。
- • 图的变化：在本次判定中，只考虑那些成本大于等于 lower 的边。
- • 动态规划状态：定义 f[y] 为从节点0到节点 y 的、只经过在线中间节点且只使用成本大于等于 lower 的边所构成的路径的最小总成本。
- • 状态初始化：f[0] 初始化为0，其他节点初始化为一个很大的数（表示不可达）。
- • 状态转移：按照拓扑顺序（通过入度为0的队列模拟）遍历节点。对于每个节点 x，遍历它的所有出边 (x, y, wt)。如果边成本 wt >= lower，则尝试更新 f[y]：f[y] = min(f[y], f[x] + wt)。
- • 判定条件：当遍历到目标节点 n-1 时，如果 f[n-1] <= k，说明存在一条路径，其瓶颈值至少为 lower 且总成本满足要求。此时二分搜索会向右移动，尝试更大的 lower 值；否则向左移动。
5. 结果提取
- • 二分搜索结束时，会找到最大的 lower 值，使得判定条件成立。这个值减1（根据 sort.Search 函数的特性）就是最终答案，即所有可行路径中瓶颈边成本的最大值。
- • 如果对于最小的 lower（值为0）都无法找到可行路径，则说明不存在任何可行路径，返回-1。

⏱️ 复杂度分析

• 时间复杂度：
- • 图的构建和预处理时间为 O(n + m)，其中 n 是节点数，m 是边数。
- • 二分搜索的迭代次数为 O(log(maxWt))，其中 maxWt 是边成本的最大值，最大可达 10^9，因此迭代次数约为 O(30) 次。
- • 在每次二分搜索的判定过程中，都需要进行一次基于拓扑排序的动态规划，时间复杂度为 O(n + m)。
- • 因此，总的时间复杂度为 O((n + m) * log(maxWt))。
• 空间复杂度：
- • 空间消耗主要用于存储图的邻接表 g、入度数组 deg、动态规划数组 f 以及队列等。
- • 这些存储结构的大小都与节点数 n 或边数 m 成线性关系。
- • 因此，总的额外空间复杂度为 O(n + m)。

💎 核心思路总结

该算法的巧妙之处在于通过二分答案将最大化瓶颈值的问题转化为一系列判定问题，并利用DAG的拓扑序特性，在每次判定时使用动态规划来高效地检查是否存在总成本满足约束的路径。预处理步骤则排除了无效节点，优化了计算效率。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
    "slices"
    "sort"
)

func findMaxPathScore(edges [][]int, online []bool, k int64)int {
    n := len(online)
    type edge struct{ to, wt int }
    g := make([][]edge, n)
    deg := make([]int, n)
    maxWt := -1
    for _, e := range edges {
        x, y, wt := e[0], e[1], e[2]
        if online[x] && online[y] {
            g[x] = append(g[x], edge{y, wt})
            deg[y]++
            if x == 0 {
                maxWt = max(maxWt, wt)
            }
        }
    }

    // 先清理无法从 0 到达的边
    q := []int{}
    for i := 1; i < n; i++ {
        if deg[i] == 0 {
            q = append(q, i)
        }
    }
    forlen(q) > 0 {
        x := q[0]
        q = q[1:]
        for _, e := range g[x] {
            y := e.to
            deg[y]--
            if deg[y] == 0 && y > 0 {
                q = append(q, y)
            }
        }
    }

    f := make([]int, n)
    ans := sort.Search(maxWt+1, func(lower int)bool {
        deg := slices.Clone(deg)
        for i := 1; i < n; i++ {
            f[i] = math.MaxInt / 2// 除 2 防止加法溢出
        }

        q := []int{0}
        forlen(q) > 0 {
            x := q[0]
            if x == n-1 {
                return f[x] > int(k)
            }
            q = q[1:]
            for _, e := range g[x] {
                y := e.to
                wt := e.wt
                if wt >= lower {
                    f[y] = min(f[y], f[x]+wt)
                }
                deg[y]--
                if deg[y] == 0 {
                    q = append(q, y)
                }
            }
        }
        returntrue
    }) - 1
    return ans
}

func main() {
    edges := [][]int{{0, 1, 5}, {1, 3, 10}, {0, 2, 3}, {2, 3, 4}}
    online := []bool{true, true, true, true}
    k := 10
    result := findMaxPathScore(edges, online, int64(k))
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math
from typing import List
import bisect

def findMaxPathScore(edges: List[List[int]], online: List[bool], k: int) -> int:
    n = len(online)
    g = [[] for _ in range(n)]  # 邻接表
    deg = [0] * n  # 入度
    max_wt = -1
    
    # 构建图，只包含两个节点都在线的边
    for e in edges:
        x, y, wt = e[0], e[1], e[2]
        if online[x] and online[y]:
            g[x].append((y, wt))
            deg[y] += 1
            if x == 0:
                max_wt = max(max_wt, wt)
    
    # 清理无法从节点 0 到达的节点（通过拓扑排序移除入度为 0 的非 0 节点）
    q = []
    for i in range(1, n):
        if deg[i] == 0:
            q.append(i)
    
    while q:
        x = q.pop(0)
        for y, wt in g[x]:
            deg[y] -= 1
            if deg[y] == 0 and y > 0:
                q.append(y)
    
    # 二分查找最大下限值
    def check(lower: int) -> bool:
        """检查是否存在路径，使得路径上所有边权都 >= lower 且总权重 <= k"""
        deg_copy = deg.copy()
        f = [math.inf] * n
        f[0] = 0
        
        q = [0]
        while q:
            x = q.pop(0)
            if x == n - 1:
                return f[x] > k  # 如果到达终点的最小权重 > k，说明 lower 太高
            
            for y, wt in g[x]:
                if wt >= lower:
                    f[y] = min(f[y], f[x] + wt)
                deg_copy[y] -= 1
                if deg_copy[y] == 0:
                    q.append(y)
        
        return True  # 如果没有到达终点的路径，说明 lower 太高
    
    # 二分查找
    left, right = 0, max_wt + 1
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            right = mid - 1
        else:
            left = mid + 1
    
    # 返回最大的满足条件的 lower 值
    return right if right >= 0else-1


# 测试示例
if __name__ == "__main__":
    edges = [[0, 1, 5], [1, 3, 10], [0, 2, 3], [2, 3, 4]]
    online = [True, True, True, True]
    k = 10
    result = findMaxPathScore(edges, online, k)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <functional>
using namespace std;

int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
    int n = online.size();
    // 定义边结构
    struct Edge {
        int to, wt;
    };
    vector<vector<Edge>> g(n);
    vector<int> deg(n, 0);
    int maxWt = -1;

    // 构建图，只包含两个节点都在线的边
    for (auto& e : edges) {
        int x = e[0], y = e[1], wt = e[2];
        if (online[x] && online[y]) {
            g[x].push_back({y, wt});
            deg[y]++;
            if (x == 0) {
                maxWt = max(maxWt, wt);
            }
        }
    }

    // 清理无法从节点 0 到达的节点（通过拓扑排序移除入度为 0 的非 0 节点）
    queue<int> q;
    for (int i = 1; i < n; i++) {
        if (deg[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto& e : g[x]) {
            int y = e.to;
            deg[y]--;
            if (deg[y] == 0 && y > 0) {
                q.push(y);
            }
        }
    }

    // 检查函数
    auto check = [&](int lower) -> bool {
        vector<int> deg_copy = deg;
        vector<long long> f(n, LLONG_MAX / 2);  // 使用 long long 防止溢出
        f[0] = 0;

        queue<int> q;
        q.push(0);

        while (!q.empty()) {
            int x = q.front();
            q.pop();

            // 如果到达终点，检查是否满足条件
            if (x == n - 1) {
                return f[x] > k;  // 如果最小权重 > k，说明 lower 太高
            }

            for (auto& e : g[x]) {
                int y = e.to;
                int wt = e.wt;
                if (wt >= lower) {
                    f[y] = min(f[y], f[x] + wt);
                }
                deg_copy[y]--;
                if (deg_copy[y] == 0) {
                    q.push(y);
                }
            }
        }
        returntrue;  // 如果没有到达终点的路径，说明 lower 太高
    };

    // 二分查找最大满足条件的 lower 值
    int left = 0, right = maxWt + 1;
    int ans = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            right = mid - 1;
        } else {
            ans = mid;  // 记录当前满足条件的 mid
            left = mid + 1;
        }
    }

    return ans;
}

int main() {
    vector<vector<int>> edges = {{0, 1, 5}, {1, 3, 10}, {0, 2, 3}, {2, 3, 4}};
    vector<bool> online = {true, true, true, true};
    long long k = 10;

    int result = findMaxPathScore(edges, online, k);
    cout << result << endl;  // 输出结果

    return0;
}