【ICPC 2023 WF】G. Lava Moat 题解

题意

题目要求在给定的三角剖分地形上，找到一条从西侧边界到东侧边界的、位于同一海拔高度的最短路径。

思路

在解决本题时，一个思路是枚举所有顶点的海拔高度 $z$，并在每个高度上构建等高线图，然后运行最短路算法。

具体来说，对于每个高度 $z$：

1. 遍历所有三角形，找出与平面 $z = \text{const}$ 相交的边，得到交点。
2. 在同一个三角形内，将这些交点按某种顺序（如按 $x$ 坐标）连接起来，形成等高线段。
3. 将所有三角形的等高线段合并，构建一个图，其中节点是交点，边是等高线段。
4. 在这个图上，从所有位于西侧（$x=0$）的节点出发，运行 Dijkstra 算法，求到任意一个东侧（$x=w$）节点的最短距离。

时间复杂度：

• 顶点数量 $n \le 5 \times 10^4$，因此有 $O(n)$ 个不同的海拔高度需要枚举。
• 对于每个高度，需要处理 $O(m) = O(n)$ 个三角形。
• 在最坏情况下，每个三角形都可能贡献两个交点，导致图中的节点数和边数达到 $O(n)$。
• 在 $O(n)$ 规模的图上运行 Dijkstra 的时间复杂度为 $O(n \log n)$。

综上，总时间复杂度到达 $O(n^2 \log n)$。对于 $n = 5 \times 10^4$ 的数据规模，$n^2$ 已经达到 $2.5 \times 10^9$，恭喜你，至此你成功TLE了。

//O(n^2 log n)
double solve_dcel(const vector<Point> &points, const vector<Triangle> &triangles, int w) {
    // 枚举每个 z，建图，跑 Dijkstra
}

问题转化

~所以我们需要更！高！效！的算法！~

题目给出一个由三角形面片组成的地形，每个顶点有唯一的海拔高度 $z$。两点之间的海拔通过三角形面片进行线性插值得到。我们的目标是找到一个海拔高度 $h$，使得存在一条从西侧（$x=0$）到东侧（$x=w$）的路径，路径上所有点的海拔都恰好为 $h$，并且这条路径的长度最短。

对于任意一个海拔高度 $h$，所有海拔为 $h$ 的点构成的集合是一些线段（或点）的并集。这些线段连接起来，会形成若干条连续的等高线。

而特别地，等高线的拓扑结构（即哪些线段是连通的）只会在经过某个顶点的海拔高度时发生变化。在两个相邻的顶点海拔 $z_i$ 和 $z_{i+1}$ 之间，等高线的连通性是静态的。在这个区间 $(z_i, z_{i+1})$ 内，任意高度 $h$ 对应的等高线长度 $L(h)$ 是关于 $h$ 的分段线性函数。

因此，全局最短路径的最小值，必然在某个顶点的海拔高度 $z_v$ 处取得，或者在某个线性区间的端点取得（而端点就是顶点海拔）。这让我们只需关注 $O(n)$ 个关键事件点（即顶点海拔），而非所有实数。

时间复杂度优化

所以我们采用事件驱动（Event-Driven） 的方法，来减少无效计算，按海拔高度 $z$ 从小到大处理。

我们将每个三角形对等高线的贡献分解为事件（Events）：

• 进入事件：当扫描线到达三角形的一个较低顶点时，一条新的等高线段（连接该顶点与对边）开始出现。
• 离开事件：当扫描线离开三角形的一个较高顶点时，对应的等高线段消失。

为了高效地维护和查询这些等高线，我们将原始三角剖分的每条无向边视为图中的一个节点。当一个三角形在某个高度区间内贡献了一条连接两条边的等高线段时，我们在对应的两个“边节点”之间建立一条带权边。

这条边的权重（即线段长度）是关于当前高度 $h$ 的线性函数：

其中，斜率 $k$ 和截距 $b$ 可以通过三角形顶点坐标和海拔精确计算得出。

到此，整个问题就变成了在一个动态变化的图上，维护从“西侧边界边”到“东侧边界边”的最短路径。由于路径长度是分段线性的，我们只需在每个事件点（顶点海拔）处，计算当前图结构下，连接东西两侧的最短路径长度（此时 $h$ 固定为该事件点的高度），并更新全局答案。

~恭喜，本题已经快成功了~

路径压缩优化

但是但是事件驱动还是容易TLE，为了高效处理动态图上的最短路径查询，需要实现一种类似路径压缩（Path Compression） 的技巧。预处理从每条边出发，在当前图结构下能直接“跳跃”到的最远边及其对应的线性函数。这使得程序在查询时可以快速拼接路径，避免在稠密图上运行完整的最短路算法，减少 Dijkstra 的总开销，从而将时间复杂度优化到可接受的范围。

Code

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>

using namespace std;

struct Link {
    int ei1, ei2;
    double fz, fc;

    bool operator<(const Link& l) const { return false; }

    Link operator+(const Link& l) const {
        assert(ei2 == l.ei1);
        return Link{ei1, l.ei2, fz + l.fz, fc + l.fc};
    }

    Link rev() const { return Link{ei2, ei1, fz, fc}; }
};

struct Edge {
    int a, b, border;
    vector<vector<Link>> skip{{}, {}};
};

int main() {
    int T, X, Y, N, M, A, B, C;
    for (cin >> T; T--;) {
        cin >> X >> Y >> N >> M;
        vector<int64_t> vx(N), vy(N), vz(N);
        for (int i = 0; i < N; i++) {
            cin >> vx[i] >> vy[i] >> vz[i];
        }

        vector<Edge> e;
        map<pair<int, int>, int> ei;
        auto edge_idx = [&](int a, int b) {
            if (ei.count({a, b})) {
                return ei[{a, b}];
            }
            int ret = ei[{a, b}] = e.size();
            e.push_back(Edge{
                .a = a,
                .b = b,
                .border = (vx[a] == 0 && vx[b] == 0) ? 1 : (vx[a] == X && vx[b] == X) ? 2 : 0
            });
            return ret;
        };

        vector<tuple<int64_t, bool, int, Link>> events;
        for (int i = 0; i < M; i++) {
            cin >> A >> B >> C;
            A--; B--; C--;
            while (vz[A] > vz[B] || vz[A] > vz[C]) {
                swap(A, B);
                swap(B, C);
            }
            bool flip = false;
            if (vz[B] > vz[C]) {
                swap(B, C);
                flip = true;
            }
            double mx = vx[A] + (vx[C] - vx[A]) * (vz[B] - vz[A]) / static_cast<double>(vz[C] - vz[A]);
            double my = vy[A] + (vy[C] - vy[A]) * (vz[B] - vz[A]) / static_cast<double>(vz[C] - vz[A]);
            double ml = hypot(mx - vx[B], my - vy[B]);

            for (int j = 0; j < 2; j++) {
                int lo = j ? B : A;
                int hi = j ? C : B;
                int zero = j ? C : A;
                double fz = ml / (vz[B] - vz[zero]);
                double fc = -fz * vz[zero];
                Link link{edge_idx(lo, hi), edge_idx(A, C), fz, fc};
                if (flip) {
                    swap(link.ei1, link.ei2);
                }
                events.push_back({vz[lo], true, lo, link});
                events.push_back({vz[hi], false, hi, link});
            }
        }
        sort(events.begin(), events.end());

        double ret = 1e18;
        int maxskip = 0;
        for (int ei_idx = 0; ei_idx < e.size(); ei_idx++) {
            do {
                e[ei_idx].skip[0].push_back(Link{ei_idx, -1, 0.0, 0.0});
                e[ei_idx].skip[1].push_back(Link{ei_idx, -1, 0.0, 0.0});
            } while (rand() % 2);
        }

        function<Link(int, int, int, int)> follow = [&](int ei, int dir, int h, int rep) {
            auto const& s = e[ei].skip[dir];
            maxskip = max<int>(maxskip, static_cast<int>(s.size()));
            if (s[h].ei2 == rep) {
                return Link{ei, ei, 1e50, 1e50};
            }
            while (h + 1 < static_cast<int>(s.size()) && s[h + 1].ei2 != -1) {
                h++;
                rep = ei;
            }
            while (h > 0 && s[h].ei2 == -1) {
                h--;
            }
            if (s[h].ei2 == -1) {
                return Link{ei, ei, 0.0, 0.0};
            }
            return s[h] + follow(s[h].ei2, dir, h, rep);
        };

        for (int i = 0; i < events.size(); i++) {
            auto [z, add, zv, link] = events[i];

            if (i > 0 && z != get<0>(events[i - 1])) {
                vector<double> border(3, 1e50);
                if (vx[zv] == 0) {
                    border[1] = 0.0;
                }
                if (vx[zv] == X) {
                    border[2] = 0.0;
                }
                for (int j = i; j < events.size(); j++) {
                    auto [z2, add2, zv2, link2] = events[j];
                    if (z2 != z || add2) {
                        break;
                    }
                    for (int dir = 0; dir < 2; dir++) {
                        link2 = link2.rev();
                        if (e[link2.ei2].a == zv || e[link2.ei2].b == zv) {
                            continue;
                        }
                        Link link3 = follow(link2.ei1, dir, 0, link2.ei1);
                        double& b = border[e[link3.ei2].border];
                        b = min(b, link3.fz * z + link3.fc);
                    }
                }
                ret = min(ret, border[1] + border[2]);
            }

            maxskip = 0;
            follow(link.ei2, 1, 0, link.ei2);
            if (add) {
                for (int h = 0; h < maxskip; h++) {
                    while (link.ei1 != -1 && static_cast<int>(e[link.ei1].skip[1].size()) <= h) {
                        link = e[link.ei1].skip[0][h - 1].rev() + link;
                    }
                    while (link.ei2 != -1 && static_cast<int>(e[link.ei2].skip[1].size()) <= h) {
                        link = link + e[link.ei2].skip[1][h - 1];
                    }
                    if (link.ei1 == -1 || link.ei2 == -1) {
                        break;
                    }
                    e[link.ei1].skip[1][h] = link;
                    e[link.ei2].skip[0][h] = link.rev();
                }
            } else {
                for (int dir = 0; dir < 2; dir++) {
                    int ei_val = dir ? link.ei2 : link.ei1;
                    for (int h = 0; h < maxskip; h++) {
                        while (ei_val != -1 && static_cast<int>(e[ei_val].skip[dir].size()) <= h) {
                            ei_val = e[ei_val].skip[dir][h - 1].ei2;
                        }
                        if (ei_val == -1) {
                            break;
                        }
                        e[ei_val].skip[!dir][h] = Link{ei_val, -1, 0.0, 0.0};
                    }
                }
            }
        }

        if (ret == 1e18) {
            cout << "impossible" << endl;
        } else {
            cout << fixed << setprecision(9) << ret << endl;
        }
    }
}