CF1163F Indecisive Taxi Fee 题解

robinyqc · 2023-11-25 12:05:59 · 题解

本文变量和题目中的一致。时间复杂度 O(n\log n + m + q)，空间复杂度 O(n + m)。

解题思路

首先基本的思路是，最短路显然是一定不经过 t 的最短路和一定经过 t 的最短路较小值。

前者是删边最短路。删边最短路的基本做法和证明可以参考《图论基础》- Alex_Wei 的 1.5.2 节。

后者更容易。设 \text{dis}(i, j) 为 i 到 j 的最短路长度。答案显然是 \min\{\text{dis}(1, t_u) + x + \text{dis}(t_v, n), \text{dis}(1, t_v) + x + \text{dis}(t_u, n)\}。

复杂度为 O\big((n + m)\log n + q\big)。由于 n, m 同阶，至此已可以通过本题。

优化复杂度

但是我们还有优化空间！我们将挑战更稠密的图。

观察复杂度瓶颈，存在两个：求解最短路是 O(m\log n) 的；对每条边算对删边最短路的贡献（区间取 \min）是 O(m\log n) 的。

求解最短路这一步前人已经优化过了：使用斐波那契堆优化 Dijkstra，即可得到 O(n\log n + m) 的最短路解法。当然，不必手写一个斐波那契堆，可以考虑使用 pb_ds 库中的 __gnu_pbds::priority_queue，采用 __gnu_pbds::thin_heap_tag 来做到相同的单源最短路复杂度。

现在问题是怎么样加速区间最值操作。由于是预处理，一定有区间取 \min 早于单点查询。区间取 \min 和区间求 \min 很像啊，于是考虑类似 ST 表的做法。设 f_{i, j} 表示将以 j 开始的长度为 2^i 的区间与 f_{i, j} 取 \min 操作。代码大概是：

void push_operation(int l, int r, int v)
{
    int len = 31 ^ __builtin_clz(r - l + 1);
    f[len][l] = min(f[len][l], v);
    f[len][r - (1 << len) + 1] = min(f[len][r - (1 << len) + 1], v);
}

这个过程显然是 O(m) 的。

将所有最初的询问操作 push 完之后，从高位到低位下放 f_{i, j}，也即 f_{i, j} \to f_{i - 1, j}，f_{i, j} \to f_{i - 1, j + 2^{i - 1}}。这个过程显然是 O(n\log n) 的。最终的 f_0 就是目标数组。

这样整个程序的时间复杂度就是 O(n\log n + m + q)。但是空间是 O(n\log n + m) 的。我不满意！

由于整个过程是离线的，考虑类似我写的这篇博客的做法。这样空间复杂度就可以压至 O(n + m) 的了。具体实现可以参考下面的代码。

代码实现

代码不是很优美，所以我加了点注释。应该能看懂吧：

#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;

#define LL long long

const int N = 200005, M = 200005;
const LL INF64 = 1e18;

struct Edge { int v, w, nxt; };
int tot = 1, h[N];
Edge e[M << 1];
void add_edge(int u, int v, int w)
{
    e[++tot] = {v, w, h[u]}; h[u] = tot;
}
#define rep(x, i) for (int i = h[x]; i; i = e[i].nxt)

// 优先队列优化的 Dijkstra 单源最短路算法
class Dijkstra
{
public:
    static void SSSP(int n, int s, LL *d, int *f, int *fid) 
    {
        for (int i = 1; i <= n; ++i) d[i] = INF64;
        for (int i = 1; i <= n; ++i) it[i] = nullptr;
        d[s] = 0;
        Q.push({s, 0});
        Node x; LL w;
        while (!Q.empty()) {
            x = Q.top();
            Q.pop();
            rep(x.id, i) {
                w = x.val + e[i].w;
                if (w < d[e[i].v]) {
                    d[e[i].v] = w, f[e[i].v] = x.id, fid[e[i].v] = i >> 1;
                    if (it[e[i].v] == nullptr) it[e[i].v] = Q.push({e[i].v, w});
                    else Q.modify(it[e[i].v], Node{e[i].v, w});
                }
            }
        }
    }

private:
    struct Node
    {
        int id;
        LL val;
        bool operator<(const Node& t) const { return val > t.val; }
    };

    // 这里为了常数使用了 __gnu_pbds::pairing_heap_tag，也就是默认 tag。
    // 实际上若需要达到 O(n lg n + m) 的复杂度应该使用 __gnu_pbds::thin_heap_tag。
    using tag = __gnu_pbds::pairing_heap_tag;
    using heap = __gnu_pbds::priority_queue<Node, less<>, tag>;
    static heap Q;
    static heap::point_iterator it[N];
};

Dijkstra::heap Dijkstra::Q;
Dijkstra::heap::point_iterator Dijkstra::it[N];

int n, m;

vector<int> SP; ///< 最短路上的节点
LL d1[N], dn[N];
int f1[N], fn[N];
int gtf(int *f, int x) { while (f[x] != x) x = f[x] = f[f[x]]; return x; }
int id[N], fid[N];
bitset<M + 3> on_path;
int val[N], q;
LL ans_del[N]; ///< 删边最短路的答案
vector<pair<int, LL> > qr[19]; ///< qr[i] 储存了所有长度为 2^i 的区间操作。

template<typename T>
void tmn(T &x, T y) { if (x > y) x = y; }

// 处理区间取 min 操作。
void push_operation(int l, int r, LL v)
{
    if (l > r) return ;
    int len = 31 ^ __builtin_clz(r - l + 1);
    qr[len].emplace_back(l, v);
    qr[len].emplace_back(r - (1 << len) + 1, v);
}

// 预处理删边最短路。
void solve_del_edge()
{
    Dijkstra::SSSP(n, 1, d1, f1, fid);
    for (int i = n; i != 1; i = f1[i]) SP.push_back(i);
    SP.push_back(1);
    reverse(SP.begin(), SP.end());
    q = SP.size();
    for (int i = 0; i < q; ++i) {
        id[SP[i]] = i + 1;
        on_path.set(fid[SP[i]]);
    }
    for (int i : SP) f1[i] = i;
    for (int i = 1; i <= n; i++) f1[i] = gtf(f1, i);
    Dijkstra::SSSP(n, n, dn, fn, fid);
    for (int i : SP) fn[i] = i;
    for (int i = 1; i <= n; i++) fn[i] = gtf(fn, i);
    for (int i = 1; i <= m; ++i) if (!on_path[i]) {
        int v = e[i * 2].v, u = e[i * 2 + 1].v, w = e[i * 2].w;
        if (id[f1[u]] > id[fn[v]]) swap(u, v);
        push_operation(id[f1[u]] + 1, id[fn[v]], 
            min(d1[u] + dn[v], d1[v] + dn[u]) + w);
    }
    memset(ans_del, 0x3f, sizeof(ans_del));
    // O(n lg n + m) 离线处理答案。
    for (int i = __lg(q); i >= 1; --i) {
        for (auto j : qr[i]) tmn(ans_del[j.first], j.second);
        int l = 1 << (i - 1);
        for (int j = q - (1 << i) + 1; j >= 1; --j) {
            tmn(ans_del[j + l], ans_del[j]);
        }
    }
    for (auto j : qr[0]) tmn(ans_del[j.first], j.second); 
}


signed main() 
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    int qq;
    cin >> n >> m >> qq;
    for (int i = 1, u, v, w; i <= m; ++i) {
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    solve_del_edge();
    int t, x;
    while (qq--) {
        cin >> t >> x;
        LL del, raw;
        if (on_path[t]) {
            del = ans_del[max(id[e[t * 2].v], id[e[t * 2 + 1].v])];
            raw = d1[n] - e[t * 2].w + x;
        }
        else {
            int v = e[t * 2].v, u = e[t * 2 + 1].v;
            del = d1[n];
            raw = min(d1[u] + x + dn[v], d1[v] + x + dn[u]);
        }
        cout << min(del, raw) << '\n';
    }
    return 0;
}

写在最后

尽管理论复杂度确实更优了，在 thin_heap 的超大常数加持下似乎并没有太大优势。在相同效率的读入下，n = 2\times 10^5, m = 1\times 10^7, q = 10^5 时，以上程序在我的电脑上开 O2 需要跑 7 s，而 Codeforces 上来自 Alex_Wei 的次优解只用跑 12 s。而且实测跑最短路的效率是差不多的（我也不知道怎么回事），主要优势在后面 O(n\log n + m) 处理区间最值操作上。