通信线路

原题链接

题目描述

在郊区有 \(N\) 座通信基站，\(P\) 条双向电缆，第 \(i\) 条电缆连接基站 \(A_i\) 和 \(B_i\)。

特别地，\(1\) 号基站是通信公司的总站，\(N\) 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 \(i\) 条电缆需要花费 \(L_i\)。

电话公司正在举行优惠活动。

农产主可以指定一条从 \(1\) 号基站到 \(N\) 号基站的路径，并指定路径上不超过 \(K\) 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

思路双端队列BFS + 二分

根据题意，一条路径的长度就被定义为第 \(k+1\) 长的边权，如果边数小于等于 \(k\)，则路径长度为 \(0\)。

所以要求的就是从节点 \(1\) 到节点 \(n\) 的路径中第 \(k+1\) 大的值的最小值，于是想到用二分。

可以用二分的情况是所求的答案在某个分界点，具有某个性质，在这个分界点的一边满足这个性质，另一边不满足

本题中的区间长度被定义为 \([0,10^6+1]\)。

为了证明我们所求的答案的确可以通过二分来找到，我们需要说明所求的答案具有某种性质，且在它的右边满足，左边不满足：

对于答案 \(x\)，需要满足的性质就是从 \(1\) 走到 \(n\) 需要经过大于 \(x\) 的边数小于等于 \(k\)，作为分界点，此时大于 \(x\) 的边数应该等于 \(k\)。
对于答案右边的区间，\(x\) 变大了，大于 \(x\) 的边数就会减小，即大于 \(x\) 的边数小于 \(k\)，同样满足性质；
对于答案左边的区间，\(x\) 变小了，大于 \(x\) 的边数就会增加，即大于 \(x\) 的边数大于 \(k\)，不满足性质。

因此可以用二分

接下来的问题就是如何判断是否满足性质？

在这里我们将大于 \(x\) 的边权设置为 \(1\)，小于等于 \(x\) 的边权设置为 \(0\)，那么只需要判断一条路径的长度是否小于等于 \(k\) 即可，如果长度小于等于 \(k\) 说明满足，否则不满足。

于是问题转换成在一幅 \(01\) 图中，找最短路径，这就可以用双端队列来做。

于是通过不断二分就能找到最小的第 \(k+1\) 大的数！

分析区间边界：

从实际情况出发可以知道，如果 \(k>\) 一条路径的边数则结果为0；
如果右边界为 \(10^6\)，则会有两种情况结果为\(10^6\)：
- 当 \(1\) 走不到 \(N\) 时，由于二分的特性，最终会返回右边界，即 \(10^6\)
- 当 \(1\) 走到 \(N\) 时，但最终的花费是 \(10^6\)，结果返回 \(10^6\)（例如 \(1\) 到 \(N\) 的路径经过两条长度都是\(10^6\) 的边，\(k=1\)，此时结果就是 \(10^6\)）

因此为了区分这两种情况需要将右边界定义成 \(10^6+1\)

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 20010;

int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool check(int x) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[1] = 0;

    deque<int> q;
    q.push_back(1);

    while (!q.empty()) {
        int t = q.front();
        q.pop_front();

        if (st[t]) continue;
        st[t] = true;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i], v = w[i] > x;
            if (dist[j] > dist[t] + v) {
                dist[j] = dist[t] + v;
                if (!v) q.push_front(j);
                else q.push_back(j);
            }
        }
    }

    return dist[n] <= k;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(h, -1, sizeof h);

    cin >> n >> m >> k;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    int l = 0, r = 1e6 + 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    if (r == 1e6 + 1) r = -1;
    cout << r << endl;

    return 0;
}

通信线路

题目描述

思路 双端队列BFS + 二分

代码

思路双端队列BFS + 二分