题解：P10440 [JOIST 2024] 环岛旅行 / Island Hopping

· · 题解

[JOIST 2024] 环岛旅行 / Island Hopping

还是 Ad-hoc 大神。

题意分析

有一个 n 个点 n-1 条边的无向图，保证图是联通的，通过 L(L \le 2n) 次询问 v 和 k，每次询问返回距离 v 第 k 近的岛屿编号，最终要求输出所有的 n-1 条边。

解法

好水，以至于我一个蒟蒻都能会。

一个非常自然的想法是采用一个类似 DFS 的做法，每次从查询距离编号为 1 的点最近的点 v，然后找到它的父亲即可。

对于每个 u 满足 u=query(v, 1)，如果我们遍历过 u，那么很显然的，u 是 v 的父亲；否则，v 是 u 的父亲。

这样就实现了在 2n 次询问之内输出所有的边。

code

#include <bits/stdc++.h>
//#include "island.h"
#define N 310
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗
int ans[N] , a[N];
bool vis[N];
int query(int v, int k);
void answer(int x, int y);
void solve(int n, int L){
    vis[1] = true;
    for(int i = 1 ; i <= n - 1 ; ++i){
        int x = query(1 , i);
        vis[x] = true;
        for(int j = 1 ; !ans[x] ; ++j){
            int y = query(x , j);
            if(vis[y])
                ans[x] = y;
            else
                ans[y] = x; 
        }
    }
    for(int i = 2 ; i <= n ; ++i)
        answer(ans[i] , i);
}