盛日辉的博客
0%

EOJ 2026. Telephone Lines（0-1BFS）

发表于 更新于 分类于

直接到最重要的地方。

题目

2026. Telephone Lines

题目翻译理解

一共有 $N$ 个电线杆，其中有 $P$ 对电线杆之间可以连电缆，电话公司可以为 $K$ 根电缆免费，最终收费为需要收费的最长的那根电缆（费用等于长度）。问连接 $1$ 号电线杆和 $n$ 号电线杆最少费用是多少？

思路

二分

题目问的是需要支付的最长的那根费用的最小值是多少，是一个最小化最大值问题，可以考虑用二分。

假设长度 $x$ 满足条件，即在长度 $\gt x$ 的电缆免费、长度 $\le x$ 的电缆收费的情况下，存在一条从 $1$ 到 $n$ 的路径，其路径上的免费电缆的根数 $\le K$ 。那么，比 $x$ 大的 $x’$ 也能满足条件，因为能消耗免费额度的电缆变少了，也意味着没有顾虑地选的电缆变多了，也就更容易找到一条从 $1$ 到 $n$ 的路径，其路径上的免费电缆的根数 $\le K$ 。

相反地，如果长度 $x$ 不满足条件，那么长度 $\lt x$ 的 $x’$ 也不满足，即找不到一条从 $1$ 到 $n$ 的路径，其路径上的免费电缆的根数 $\le K$ 。

因此，这题的答案满足单调性，可以用二分。

最短路

二分的范围容易确定，就是在最短和最长的长度之间——当然，如果 $1$ 到 $n$ 本身就不连通的情况不能忘了。

注意到上面单调性讨论里的话，

能消耗免费额度的电缆变少了，也意味着没有顾虑地选的电缆变多了

这说明，当我们假设了一个答案 $m$ ，比 $m$ 大的需要消耗一个额度，而小于等于 $m$ 的不用，这提示我们，可以将大于 $m$ 的边看做边权为 $1$ ，小于等于 $m$ 的边权认为是 $0$ ，这样，问题就转换成了寻找从 $1$ 到 $n$ 的最短路，判断是否小于等于 $K$。如果判断为真，说明 $m$ 大了，要缩小。

Dijkstra

最基本的单源最短路就是 Dijkstra 了。不多说，直接上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def check_dijkstra(m: int) -> bool:
    import heapq
    dist = [INF] * (n + 1)
    dist[1] = 0
    h = [(0, 1)]
    while h:
        d, x = heapq.heappop(h)
        for y, l in g[x]:
            l = 1 if l > m else 0
            nd = dist[x] + l
            if nd >= dist[y]:
                continue
            dist[y] = nd
            heapq.heappush(h, (nd, y))
    return dist[n] <= k

0-1BFS

终于到这篇最重要的地方了。

0-1BFS 主要是在边权只有 $0$ 和 $1$ 的单源最短路问题上对 BFS 的优化。和普通的 BFS 相比，在代码上的差别就是在入队的方式上：

  • 如果边权是 $1$，加到队尾；
  • 如果边权是 $0$，加到队头。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def check_01bfs(m: int) -> bool:
    from collections import deque
    dist = [INF] * (n + 1)
    dist[1] = 0
    q = deque([1])
    while q:
        u = q.popleft()
        for v, l in g[u]:
            l = 1 if l > m else 0
            nd = dist[u] + l
            if nd < dist[v]:
                dist[v] = nd
                if l == 1:
                    q.append(v)
                else:
                    q.appendleft(v)
    return dist[n] <= k

尝试小小的理解和解释一下：

众所周知，广度优先搜索可以看做是水面涟漪一层层向外扩展的过程。结合图的最短路问题特别是边权都是 $1$ 和只有 $0/1$ 的问题来说，每一层的不同结点的路径都是相同的，相邻两层的结点一定是先访问内层的再访问外层的，内层的结点路径比外层小，同一层结点的访问没有先后顺序。那么，假设结点 $u$ 与 $v$ 相连边权是 $1$ ，当访问到 $u$ 的时候，$v$ 一定不是和 $u$ 在同一层，而 $u$ 的这一层可能还没有访问完，所以要比较后面访问 $v$ ，也就是把它加到队尾；但如果它们之间的边权是 $0$ ，说明 $v$ 和 $u$ 是在同一层，那么就要相对早一些访问 $v$ ，因此加到队头。

一个结点最多入队两次，一次是队头一次是队尾。用我这个水波涟漪的模型也好理解，因为同时在队列中的最多只有两层，$v$ 要么先因为一个边权为 $1$ 的入队尾然后因为一个边权为 $0$ 的入队头，然后访问到了之后，就确定了 $v$ 的最短路了呀。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# n 个电线杆，p 个可连接的边，电话公司可以为 k 根电缆的免费
n, p, k = map(int, input().split())


# 二分 + 最短路
# 在 [mn, mx] 上二分答案，
# 找最大的电缆长度，大于这个长度免费
# check(m)
# 将长度 > m 的记为 1，其他记为 0
# 看从 1 到 n 的最短路径是否小于等于 k
# <=> 能否用 k 个免费到达终点
# true: m 大了，false：m 小了
def check_01bfs(m: int) -> bool:
    from collections import deque
    dist = [INF] * (n + 1)
    dist[1] = 0
    q = deque([1])
    while q:
        u = q.popleft()
        for v, l in g[u]:
            l = 1 if l > m else 0
            nd = dist[u] + l
            if nd < dist[v]:
                dist[v] = nd
                if l == 1:
                    q.append(v)
                else:
                    q.appendleft(v)
    return dist[n] <= k

def check_dijkstra(m: int) -> bool:
    import heapq
    dist = [INF] * (n + 1)
    dist[1] = 0
    h = [(0, 1)]
    while h:
        d, x = heapq.heappop(h)
        for y, l in g[x]:
            l = 1 if l > m else 0
            nd = dist[x] + l
            if nd >= dist[y]:
                continue
            dist[y] = nd
            heapq.heappush(h, (nd, y))
    return dist[n] <= k


INF = 10 ** 20
g = [[] * (n + 1) for _ in range(n + 1)]
mx = 0
for _ in range(p):
    a, b, l = map(int, input().split())
    g[a].append((b, l))
    g[b].append((a, l))
    if l > mx:
        mx = l

left, right = 0, mx
while left <= right:
    mid = (left + right) // 2
    # if check_dijkstra(mid):
    if check_01bfs(mid):
        right = mid - 1
    else:
        left = mid + 1
print(left if left < mx else -1)

其他

这题和 3681. 中位数 有异曲同工之处在于，它们都将权值转换、映射到了两个特殊值上，这题是边权变为 $0$ 和 $1$ 算最短路，另题是点权变为 $1$ 和 $-1$ 考虑中位数，我觉得还挺妙的。那道题的题解在这里。