题解：P14414 [JOISC 2015] 导航 / Navigation【通信题暂无法评测】

Emily1234 · 2025-11-15 09:20:19 · 题解

题解：P14414 [JOISC 2015] 导航 / Navigation【通信题暂无法评测】

首先求关

问题核心分析

这是一道通信题，需要设计两套独立策略：

安娜（Anna）：在树状结构的每个岛屿上设置旗帜值（0~N），旗帜值需能引导布鲁诺找到目标岛 T。

布鲁诺（Bruno）：仅通过当前岛 S 的旗帜值、相邻岛的编号及旗帜值，判断 S 是否为 T；若不是，选择通往 T 的最短路径的下一步。

树的最短路径特性是关键：两点间最短路径唯一，布鲁诺只需从当前岛向 “更靠近 T” 的方向移动即可。

核心策略设计（适用于所有子任务，重点满足 K=4 约束）

我们利用距离标记法：

• 安娜：计算每个岛屿到目标岛 T 的距离 d[u]（T 自身距离为 0），将旗帜值设为 d[u] % 2（仅用 0/1，满足 K=4 的 V∈{0,1} 约束）。
• 布鲁诺：
  1. 若当前岛 S 的旗帜值为 0（距离 T 为 0，即 S=T），直接返回 S。
  2. 若不为 0，寻找相邻岛中旗帜值与当前值不同的岛（因距离 T 每减少 1，距离的奇偶性翻转），该岛即为最短路径的下一步。

具体实现

Anna.cpp （安娜的旗帜设置）

思路

• 先将树构建为邻接表，便于遍历。
• 用 BFS 计算每个岛到 T 的距离（BFS 适合树的最短距离计算，且时间复杂度 O (N)，支持 N=1e5）。
• 调用 Flag 函数，为每个岛设置旗帜值 d[u] % 2。

介于无法评测，我的代码也不一定准确

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

// 全局变量：邻接表、距离数组（支持 N=1e5）
static vector<int> adj[100001];
static int d[100001];

// 安娜的主函数
void Anna(int K, int N, int T, int A[], int B[]) {
    // 1. 构建邻接表
    for (int i = 0; i < N-1; ++i) {
        int u = A[i], v = B[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 2. BFS 计算每个岛到 T 的距离
    queue<int> q;
    for (int i = 1; i <= N; ++i) d[i] = -1; // 初始化距离为 -1（未访问）
    d[T] = 0;
    q.push(T);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (d[v] == -1) { // 未访问过
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }

    // 3. 为每个岛设置旗帜（V = d[u] % 2，满足 K=4 的 0/1 约束）
    for (int u = 1; u <= N; ++u) {
        Flag(u, d[u] % 2);
    }
}