「POI2018 R1」地铁路线图 Subway design 题解

题目大意

给定 $n$ 个地铁站，编号 $1$ 到 $n$，其中 $1$ 号是火车站，$n$ 号是机场。已知：

• $d_i$：从火车站到 $i$ 号站的最短距离（$i=2,3,\ldots,n-1$）
• $l_i$：从机场到 $i$ 号站的最短距离（$i=2,3,\ldots,n-1$）

地铁网络是一棵树（$n-1$ 条边，连通无环）。要求判断是否存在满足距离约束的树，如果存在输出任意一种方案。

核心观察

1. 关键等式

设 $D = \text{dist}(1, n)$ 为火车站到机场的距离。

对于任意站 $i$（$2 \le i \le n-1$）：

• 如果 $i$ 在 $1 \to n$ 的路径上，则 $d_i + l_i = D$
• 如果 $i$ 不在 $1 \to n$ 的路径上，则 $d_i + l_i > D$

证明：在树中，$1 \to i \to n$ 的路径长度是 $d_i + l_i$，而 $1 \to n$ 有唯一最短路径 $D$。如果 $i$ 在这条路径上，则路径就是 $1 \to i \to n$；否则需要绕路，距离更大。

2. 挂接点的性质

对于不在路径上的点 $i$，设它挂在路径上的点 $p$ 上，则有：

• $d_i = d_p + w$（$w > 0$ 是挂接边的长度）
• $l_i = l_p + w$

两式相减得：$d_i - l_i = d_p - l_p$

这意味着：不在路径上的点必须与路径上某个点的 $d-l$ 值相同。

算法步骤

步骤 1：确定 $D$

计算 $D = \min\limits_{2 \le i \le n-1} (d_i + l_i)$

如果找不到这样的 $D$（即 $n=2$ 时没有中间点），则 $D$ 可以是任意正数，通常取 $1$。

步骤 2：找出路径上的点

路径上的点满足 $d_i + l_i = D$，包括：

• 站 $1$：$d_1 = 0, l_1 = D$
• 站 $n$：$d_n = D, l_n = 0$
• 中间站 $i$：$d_i + l_i = D$

将这些点按 $d$ 值从小到大排序，就得到路径顺序 $1 = p_1, p_2, \ldots, p_k = n$。

步骤 3：检查路径合法性

• $d$ 值必须严格递增
• $l$ 值必须严格递减（因为 $l_i = D - d_i$）
• 相邻点间的边权 $w = d_{p_{j+1}} - d_{p_j}$ 必须是正整数

步骤 4：处理不在路径上的点

对于每个不在路径上的点 $i$：

1. 计算 $\text{diff} = d_i - l_i$
2. 在路径上寻找满足 $d_p - l_p = \text{diff}$ 且 $d_p < d_i$ 的点 $p$
3. 如果找到，计算边权 $w = d_i - d_p = l_i - l_p$，必须 $w > 0$
4. 添加边 $(p, i, w)$

步骤 5：最终检查

• 必须有恰好 $n-1$ 条边
• 所有边权为正整数
• 图连通（构造方法保证）

正确性证明

必要性

如果存在满足条件的树，那么：

1. $D$ 必须等于某个 $d_i + l_i$ 的最小值（路径上的点）
2. 路径点按 $d$ 排序后必须严格递增
3. 挂接点必须满足 $d_i - l_i = d_p - l_p$ 且 $d_p < d_i$

充分性

按照上述方法构造的树：

• 路径部分保证了 $1 \to n$ 的距离为 $D$
• 挂接部分保证了每个点 $i$ 到 $1$ 和 $n$ 的距离正确
• 树结构保证了距离的唯一性

复杂度分析

• 排序路径点：$O(n \log n)$
• 处理挂接点：$O(n \log n)$（使用 map）
• 总复杂度：$O(n \log n)$，可处理 $n \le 5 \times 10^5$

代码实现细节

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

typedef long long ll;
const int MAXN = 500005;

int n;
ll d[MAXN], l[MAXN];
bool on_path[MAXN];
vector<pair<ll, int>> path_nodes; // (d[i], i)
map<ll, int> path_by_diff; // d[u] - l[u] -> 最大的d[u]对应的u

struct Edge {
    int a, b;
    ll c;
};

vector<Edge> edges;

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

    cin >> n;
    for (int i = 2; i <= n-1; i++) cin >> d[i];
    for (int i = 2; i <= n-1; i++) cin >> l[i];

    // 特殊情况处理
    if (n == 2) {
        cout << "TAK\n";
        cout << "1 2 1\n";
        return 0;
    }

    // 步骤1：计算D
    ll D = 1e18;
    for (int i = 2; i <= n-1; i++) {
        D = min(D, d[i] + l[i]);
    }

    // 步骤2：找出路径上的点
    d[1] = 0; l[1] = D;
    d[n] = D; l[n] = 0;

    for (int i = 1; i <= n; i++) {
        if (i >= 2 && i <= n-1) {
            if (d[i] + l[i] == D) {
                path_nodes.emplace_back(d[i], i);
                on_path[i] = true;
            }
        } else {
            path_nodes.emplace_back(d[i], i);
            on_path[i] = true;
        }
    }

    // 步骤3：检查路径合法性
    sort(path_nodes.begin(), path_nodes.end());
    
    // 检查d值严格递增
    for (int i = 1; i < (int)path_nodes.size(); i++) {
        if (path_nodes[i].first == path_nodes[i-1].first) {
            cout << "NIE\n";
            return 0;
        }
    }
    
    // 检查首尾
    if (path_nodes[0].second != 1 || path_nodes.back().second != n) {
        cout << "NIE\n";
        return 0;
    }

    // 构建路径边
    for (int i = 1; i < (int)path_nodes.size(); i++) {
        int u = path_nodes[i-1].second;
        int v = path_nodes[i].second;
        ll w = path_nodes[i].first - path_nodes[i-1].first;
        if (w <= 0) {
            cout << "NIE\n";
            return 0;
        }
        edges.push_back({u, v, w});
    }

    // 记录路径上各diff对应的最大d的点
    for (auto& p : path_nodes) {
        int u = p.second;
        ll diff = d[u] - l[u];
        if (path_by_diff.find(diff) == path_by_diff.end() || 
            d[path_by_diff[diff]] < d[u]) {
            path_by_diff[diff] = u;
        }
    }

    // 步骤4：处理挂接点
    for (int i = 2; i <= n-1; i++) {
        if (!on_path[i]) {
            ll diff = d[i] - l[i];
            if (path_by_diff.find(diff) == path_by_diff.end()) {
                cout << "NIE\n";
                return 0;
            }
            int p = path_by_diff[diff];
            if (d[p] >= d[i]) {
                cout << "NIE\n";
                return 0;
            }
            ll w = d[i] - d[p];
            if (w != l[i] - l[p] || w <= 0) {
                cout << "NIE\n";
                return 0;
            }
            edges.push_back({p, i, w});
        }
    }

    // 步骤5：最终检查
    if ((int)edges.size() != n-1) {
        cout << "NIE\n";
        return 0;
    }

    // 输出结果
    cout << "TAK\n";
    for (auto& e : edges) {
        cout << e.a << " " << e.b << " " << e.c << "\n";
    }

    return 0;
}

样例分析

样例输入

7
6 6 2 2 1
5 3 5 1 4

处理过程

1. 计算 $D = \min(6+5, 6+3, 2+5, 2+1, 1+4) = \min(11,9,7,3,5) = 3$
2. 路径点：满足 $d_i + l_i = 3$ 的点是 $d=2,l=1$ 和 $d=1,l=2$ 等，加上站1和站7
3. 构建路径，挂接其他点
4. 输出6条边构成树

总结

本题的关键在于利用树的路径结构特性，通过距离约束反推拓扑结构。这种"主路径+挂接点"的构造方法在树形问题中很常见，掌握后可以解决许多类似题目。

算法的正确性依赖于树中距离关系的严格数学性质，通过逐步验证这些性质，可以保证构造出的解满足所有约束条件。