盛日辉的博客
0%

EOJ 2026. Telephone Lines（0-1BFS）

发表于 更新于 分类于

直接到最重要的地方。

题目

2026. Telephone Lines

题目翻译理解

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

思路

二分

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

假设长度 $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$ 的最短路了呀。

完整代码

Python

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)

C++

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int to, length;
};

const int N = 1005;
const int INF = 0x3f3f3f3f;
int n, p, k;
vector<edge> g[N];

bool check_01bfs(const int& m)
{
    deque<int> q;
    int dist[N];
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    q.push_back(1);
    while(q.size())
    {
        int u = q.front();
        q.pop_front();
        for(const edge& e: g[u])
        {
            int v = e.to, l = e.length > m ? 1 : 0;
            int nd = dist[u] + l;
            if(nd < dist[v])
            {
                dist[v] = nd;
                if(l == 1) q.push_back(v);
                else q.push_front(v);
            }
        }
    }
    return dist[n] <= k;
}

bool check_dijkstra(const int& m)
{
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> h;
    h.push({0 , 1});
    while(h.size())
    {
        pair<int, int> p = h.top();
        h.pop();
        int d = p.first, x = p.second;
        for(const edge& e : g[x])
        {
            int y = e.to, l = e.length > m ? 1 : 0;
            int nd = d + l;
            if (nd >= dist[y]) continue;
            dist[y] = nd;
            h.push({nd, y});
        }
    }
    return dist[n] <= k;
}

int main()
{
    cin >> n >> p >> k;

    int mx = 0;
    while(p--)
    {
        int a, b, l; cin >> a >> b >> l;
        g[a].push_back({b, l});
        g[b].push_back({a, l});
        mx = mx > l ? mx : l;
    }

    int left = 0, right = mx;
    while(left <= right)
    {
        int mid = left + ((right - left) >> 1);
//        if(check_dijkstra(mid))
        if(check_01bfs(mid))
            right = mid - 1;
        else
            left = mid + 1;
    }
    cout << (left <= mx ? left : -1) << "\n";
    return 0;
}

OJ小漏洞

将代码最后的 left >= mx 写成 left > mx 在 OJ 平台上也能AC。

但这样是不对的。

一个简单的用例，

1
2
2 1 0
1 2 10

$K=0$ 且 $1$ 到 $n$ 可达的情况，二分结束之后，$left$ 等于 $mx$ ，应该输出 $left$ ，但 $left<mx$ 会输出错误的 $-1$ 。

其他

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