P1186 玛丽卡_牛客博客

题目

算法标签: 最短路, 优化, 线段树

思路

根据题意, 计算的是删除任意一条边的最短路的最大值, 很明显删除最短路径以外的边才会对最短路有影响, 暴力的方法就是删除所有边, 每次删除一条边计算依次最短路
不难发现, 最终删边后的路径一定经过至少一条删边前最短路径之外的边，那么可以考虑经过一条确定边的最短路径
具体的算法思路

计算从节点 $1$ 到 $n$ 的最短路径 $d_1$ , 计算从节点 $n$ 到其他节点的最短路径 $d_2$
找到原最短路径的所有节点和边
对于每个非最短路径的边 $(u, v)$ , 计算能替代原最短路的哪些边
使用线段树维护每条边被删除后的最小替代值
计算最大值

时间复杂度 $O(n ^ 2 + m log n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1010, INF = 0x3f3f3f3f;

int n, m, w[N][N];
int dist_s[N], dist_t[N];
bool vis[N];
int tr[N << 2];
int ans;
int fa[N], pre[N], id[N], cnt;

void dijkstra(int s, int d[]) {
   
    priority_queue<PII, vector<PII>, greater<>> q;
    memset(d, 0x3f, sizeof(int) * (n + 1));
    memset(vis, false, sizeof vis);
    d[s] = 0;
    q.push({
   0, s});

    while (!q.empty()) {
   
        auto [dis, u] = q.top();
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int v = 1; v <= n; ++v) {
   
            if (w[u][v] == INF) continue;
            if (d[u] + w[u][v] < d[v]) {
   
                d[v] = d[u] + w[u][v];
                if (s == 1) pre[v] = u;
                q.push({
   d[v], v});
            }
        }
    }
}

int find(int u) {
   
    if (fa[u] != u) fa[u] = find(fa[u]);
    return fa[u];
}

void build(int u, int l, int r) {
   
    tr[u] = INF;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void add_tag(int u, int val) {
   
    tr[u] = min(tr[u], val);
}

void push_down(int u) {
   
    if (tr[u] != INF) {
   
        add_tag(u << 1, tr[u]);
        add_tag(u << 1 | 1, tr[u]);
        tr[u] = INF;
    }
}

void update(int u, int l, int r, int ql, int qr, int val) {
   
    if (l >= ql && r <= qr) {
   
        return add_tag(u, val);
    }
    push_down(u);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(u << 1, l, mid, ql, qr, val);
    if (qr > mid) update(u << 1 | 1, mid + 1, r, ql, qr, val);
}

void query(int u, int l, int r) {
   
    if (l == r) {
   
        ans = max(ans, tr[u]);
        return;
    }
    push_down(u);
    int mid = (l + r) >> 1;
    query(u << 1, l, mid);
    query(u << 1 | 1, mid + 1, r);
}

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

    cin >> n >> m;
    memset(w, 0x3f, sizeof w);

    for (int i = 0; i < m; ++i) {
   
        int u, v, val;
        cin >> u >> v >> val;
        if (w[u][v] > val) {
   
            w[u][v] = w[v][u] = val;
        }
    }

    dijkstra(1, dist_s);
    dijkstra(n, dist_t);

    for (int i = 1; i <= n; ++i) fa[i] = pre[i];

    // 从n向1号节点为每个节点分配编号
    for (int i = n; i != 0; i = pre[i]) {
   
        id[i] = ++cnt;
        fa[i] = i;
        // 移除最短路上的边
        if (pre[i]) {
   
            w[i][pre[i]] = w[pre[i]][i] = INF;
        }
    }

    if (cnt == 0) {
   
        cout << 0 << endl;
        return 0;
    }

    build(1, 2, cnt);

    for (int i = 1; i <= n; ++i) {
   
        for (int j = i + 1; j <= n; ++j) {
   
            // 跳过最短路上的边
            if (w[i][j] == INF) continue;

            int u = id[find(i)];
            int v = id[find(j)];

            if (u == v) continue;

            if (v < u) swap(u, v);

            int nw = min(dist_s[i] + w[i][j] + dist_t[j],
                         dist_s[j] + w[i][j] + dist_t[i]);
            update(1, 2, cnt, u + 1, v, nw);
        }
    }

    ans = 0;
    query(1, 2, cnt);

    if (ans == INF) ans = 0;
    cout << ans << "\n";

    return 0;
}

*提示

为什么线段树的区间编号是从 $2$ 开始而不是从 $1$ 开始?
线段树维护的是最短路径上相邻段之间的路径信息, 也就是将最短路按照编号划分为若干段, 假设最短路上有 $k$ 个点, 那么将最短路划分为 $k - 1$ 段, 线段树区间就是 $[2, k]$

P1186 玛丽卡

目录

题目

算法标签: 最短路, 优化, 线段树

思路

代码

*提示