题解：测地集问题（Geodetic Set Problem）

一、题目分析

本题要求判断给定的顶点子集 ( D ) 是否为图的测地集。测地集的定义是：集合 ( D ) 中所有顶点对的最短路径（测地线）上的顶点的并集必须包含图的所有顶点。即，对于图中任意顶点 ( v )，必须存在 ( D ) 中的两个顶点 ( u ) 和 ( w )，使得 ( v ) 在 ( u ) 和 ( w ) 的最短路径上。

二、解题思路

1. 最短路径计算：
   使用 Floyd-Warshall 算法 预处理任意两点之间的最短路径长度。该算法可以在 ( O(n^3) ) 的时间复杂度内计算出所有顶点对的最短路径，适用于顶点数 ( n \leq 40 ) 的情况。

2. 判断顶点是否在最短路径上：
   对于任意三个顶点 ( u )、( v )、( w )，若 ( \text{dist}(u, w) + \text{dist}(w, v) = \text{dist}(u, v) )，则 ( w ) 在 ( u ) 和 ( v ) 的某条最短路径上。利用这一性质，预处理所有顶点对 ( (u, v) ) 的最短路径上的顶点集合。

3. 位运算优化集合表示：
   用 位掩码（Bitmask） 表示每个顶点对 ( (u, v) ) 的最短路径上的顶点集合。例如，顶点 ( k ) 在 ( u ) 和 ( v ) 的最短路径上，则将第 ( k-1 ) 位设为 1。通过位或运算（|）合并所有顶点对的位掩码，最终判断是否覆盖所有顶点（即掩码为 ( 2^n - 1 )）。

三、代码实现

#include <iostream>
#include <cstring>
#include <string>
#include <sstream>
using namespace std;

const int MAXN = 50;
const int INF = 0x3f3f3f3f;
int g[MAXN][MAXN];  // 存储最短路径长度
long long f[MAXN][MAXN];  // 位掩码：记录(u, v)最短路径上的顶点

int main() {
    int n;
    cin >> n;
    cin.ignore();  // 读取行末换行符

    // 初始化邻接矩阵（Floyd-Warshall预处理）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            g[i][j] = (i == j) ? 0 : INF;
        }
    }

    // 读取邻接表并构建初始图（无向图，边权为1）
    for (int i = 1; i <= n; i++) {
        string line;
        getline(cin, line);
        istringstream iss(line);
        int neighbor;
        while (iss >> neighbor) {
            g[i][neighbor] = 1;
            g[neighbor][i] = 1;
        }
    }

    // Floyd-Warshall算法计算最短路径
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (g[i][j] > g[i][k] + g[k][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                }
            }
        }
    }

    // 预处理每个顶点对(u, v)的最短路径上的顶点（位掩码表示）
    for (int u = 1; u <= n; u++) {
        for (int v = 1; v <= n; v++) {
            for (int w = 1; w <= n; w++) {
                if (g[u][v] == g[u][w] + g[w][v]) {  // w在u-v的最短路径上
                    f[u][v] |= (1LL << (w - 1));  // 设置第w-1位为1
                }
            }
        }
    }

    int m;
    cin >> m;
    cin.ignore();  // 读取行末换行符

    // 处理每个测试用例
    while (m--) {
        string line;
        getline(cin, line);
        istringstream iss(line);
        int da[MAXN], cnt = 0;
        while (iss >> da[cnt++]);  // 读取顶点集合D

        long long ans = 0;
        // 合并D中所有顶点对的最短路径上的顶点（位或运算）
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < cnt; j++) {
                ans |= f[da[i]][da[j]];
            }
        }

        // 判断是否覆盖所有顶点（位掩码全为1）
        if (ans == ((1LL << n) - 1)) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }

    return 0;
}

四、代码解析

1. 输入处理：

   • 使用 getline 和 istringstream 读取每行的邻接顶点，处理含空格的输入。
   • 无向图的边权初始化为 1（因为边数即距离）。

2. Floyd-Warshall算法：

   • 三层循环更新最短路径长度 g[i][j]，确保任意两点的最短路径被正确计算。

3. 位掩码预处理：

   • 对于每个顶点对 (u, v)，遍历所有顶点 w，若 w 在 u-v 的最短路径上，则将 f[u][v] 的第 w-1 位设为 1。

4. 测试用例判断：

   • 对于每个顶点集合 D，计算所有顶点对的位掩码的或结果 ans。若 ans 包含所有 n 位（即 ans == 2^n - 1），则输出 "yes"，否则输出 "no"。

五、关键点总结

• 最短路径判断：利用 Floyd 算法预处理所有顶点对的最短路径，通过路径长度和判断顶点是否在最短路径上。
• 位运算优化：用位掩码高效表示顶点集合，通过位或运算快速合并集合，避免显式集合操作的复杂性。
• 输入处理技巧：使用 stringstream 解析含空格的输入行，适用于不规则的输入格式。

该解法通过预处理和位运算优化，高效地解决了测地集的判断问题，时间复杂度为 ( O(n^3 + m \cdot k^2) )（其中 ( k ) 为测试用例中顶点集的平均大小），适用于题目给定的数据范围。