【字母建图，Floyd】P16778 Friends

题意概括

世界上有 $N$ 个人，每个人有一个由大写英文字母组成的名字。

如果两个人的名字中至少包含一个相同字母，那么这两个人是朋友。

现在有 $Q$ 次询问。每次给出两个人 $A,B$，要求求出从 $A$ 到 $B$ 的最短友谊链长度。如果不存在友谊链，则输出 $-1$。

友谊链的长度指链中包含的人数。因此，如果两个人本身就是朋友，答案为 $2$。

由于 $N$ 最大可以达到 $5\times 10^4$，而询问数量 $Q$ 最大也可以达到 $5\times 10^4$，不能直接在所有人组成的图上进行最短路查询。

样例分析

在第一组样例中，LIZZIE 与 KEVIN 都包含字母 E，所以两人直接是朋友，最短友谊链为

$$\text{LIZZIE}\rightarrow\text{KEVIN}.$$

链中共有 $2$ 个人，所以答案为 $2$。

对于 LIZZIE 与 BOHDAN，两人的名字没有公共字母，不能直接连接。但是存在友谊链

$$\text{LIZZIE}\rightarrow\text{KEVIN}\rightarrow\text{BOHDAN}. $$

LIZZIE 与 KEVIN 都包含字母 I，KEVIN 与 BOHDAN 都包含字母 N，所以这条链合法，长度为 $3$。

这个例子说明，中间人的作用是把两个不同的字母连接起来。因此，可以不直接研究人数最多达到 $5\times 10^4$ 的人物图，而是研究只有 $26$ 个节点的字母图。

算法思路

整体思路

把每个大写英文字母看成一个节点。

如果某个人的名字中同时包含字母 $x$ 和字母 $y$，就在字母 $x$ 与字母 $y$ 之间连接一条长度为 $1$ 的边。

这样可以得到一张只有 $26$ 个节点的无向图。使用 Floyd 算法求出任意两个字母之间的最短距离。

对于一次询问 $(A,B)$，枚举名字 $S_A$ 中的字母 $x$ 和名字 $S_B$ 中的字母 $y$。如果字母图中 $x$ 到 $y$ 的最短距离为 $d_{x,y}$，那么对应的友谊链长度为

$$d_{x,y}+2.$$

对所有字母组合取最小值即可。

为什么不能直接建立人物图

最直接的想法是把每个人看成一个节点。如果两个人的名字中存在相同字母，就在两人之间连边。

但是判断所有人的两两关系需要枚举

$$\binom{N}{2}$$

对人物。

当 $N=5\times 10^4$ 时，两两比较的数量达到 $O(N^2)$，无法通过。

即使已经建立了人物图，每次询问再进行一次 BFS，最坏总复杂度也会达到 $O(Q(N+M))$，同样无法接受。

因此，需要利用字母种类只有 $26$ 种这一条件压缩图的规模。

建立字母图

设字母图中的节点为 $0$ 到 $25$，分别对应字母 A 到 Z。

对于每个人的名字，先找出名字中出现过的所有不同字母。

如果一个名字中同时出现字母 $x$ 和字母 $y$，就在字母图中连接一条无向边

$$x\leftrightarrow y.$$

边权为 $1$。

例如名字 KEVIN 包含字母

$$\{\text{K},\text{E},\text{V},\text{I},\text{N}\}.$$

因此这些字母之间两两连边。

这条边表示，可以选择这个人作为友谊链中的一个中间人，把通过字母 $x$ 到达他的过程，转换成通过字母 $y$ 离开他的过程。

友谊链怎样对应字母路径

考虑一条从 $A$ 到 $B$ 的友谊链

$$X_1=A,X_2,\ldots,X_k=B.$$

因为相邻两个人是朋友，所以对于每个 $i$，都能选择一个同时出现在 $X_i$ 和 $X_{i+1}$ 名字中的字母，记为 $c_i$。

于是得到字母序列

$$c_1,c_2,\ldots,c_{k-1}.$$

其中：

• $c_1$ 出现在起点 $A$ 的名字中；
• $c_{k-1}$ 出现在终点 $B$ 的名字中；
• 对于每个中间人 $X_i$，其名字中同时包含 $c_{i-1}$ 和 $c_i$。

因此，字母图中存在边

$$c_{i-1}\leftrightarrow c_i.$$

所以，一条包含 $k$ 个人的友谊链，对应一条包含 $k-2$ 条边的字母路径。

反过来，假设字母图中存在一条路径

$$c_0\rightarrow c_1\rightarrow\cdots\rightarrow c_d, $$

其中 $c_0$ 出现在 $A$ 的名字中，$c_d$ 出现在 $B$ 的名字中。

由于字母图中每条边 $c_{i-1}\leftrightarrow c_i$ 都是由某个人的名字产生的，所以可以选择一个同时包含这两个字母的人作为中间人。

于是能够构造出友谊链

$$A\rightarrow P_1\rightarrow P_2\rightarrow\cdots\rightarrow P_d\rightarrow B. $$

这条链包含的人数为

$$d+2.$$

因此，若从字母 $x$ 到字母 $y$ 的最短距离为 $d_{x,y}$，那么从包含 $x$ 的人到包含 $y$ 的人的最短友谊链长度为

$$d_{x,y}+2.$$

查询答案

对于一次询问 $(A,B)$，枚举

$$x\in S_A,\qquad y\in S_B.$$

答案为

$$\operatorname{ans}(A,B) = \min_{\substack{x\in S_A\\y\in S_B}} \left(d_{x,y}+2\right). $$

如果不存在任何可达的字母组合，则答案为 $-1$。

如果两个人的名字中有公共字母，可以选择 $x=y$。由于

$$d_{x,x}=0,$$

所以答案为

$$0+2=2,$$

正好表示两个人直接是朋友。

进一步预处理

直接枚举两个名字中的所有字母，单次询问最多需要检查 $20\times20=400$ 对字母。这个复杂度本身已经可以通过。

还可以预处理

$$f_{i,c} = \min_{x\in S_i}d_{x,c}.$$

它表示从第 $i$ 个人名字中的任意字母出发，到字母 $c$ 的最短距离。

对于询问 $(A,B)$，只需要枚举 $B$ 名字中的字母 $y$：

$$\operatorname{ans}(A,B) = \min_{y\in S_B}f_{A,y}+2. $$

这样单次询问最多枚举 $20$ 个字母。

算法流程

对于每个测试用例：

1. 初始化 $26\times26$ 的距离数组 $d$。
2. 对所有字母 $i$，令 $d_{i,i}=0$，其他距离设为无穷大。
3. 读入每个人的名字，记录其中出现的不同字母。
4. 对于同一个名字中的任意两个字母 $x,y$，令 $d_{x,y}=1$。
5. 使用 Floyd 算法求出所有字母对之间的最短距离。
6. 对每个人 $i$ 和每个字母 $c$，预处理$$f_{i,c}=\min_{x\in S_i}d_{x,c}.$$
7. 对每次询问 $(A,B)$，枚举名字 $S_B$ 中出现的字母 $c$，计算$$\min_{c\in S_B}f_{A,c}.$$
8. 如果结果为无穷大，输出 $-1$，否则输出结果加 $2$。

正确性说明

引理一

任意一条长度为 $k$ 的友谊链，都对应字母图中一条长度为 $k-2$ 的路径。

证明

设友谊链为

$$X_1=A,X_2,\ldots,X_k=B.$$

对于每对相邻的人 $X_i,X_{i+1}$，选择一个同时出现在两人名字中的字母 $c_i$。

对于每个中间人 $X_i$，他的名字中同时包含 $c_{i-1}$ 和 $c_i$，所以建图时一定连接了边

$$c_{i-1}\leftrightarrow c_i.$$

因此

$$c_1\rightarrow c_2\rightarrow\cdots\rightarrow c_{k-1} $$

是字母图中的一条路径，共有 $k-2$ 条边。引理得证。

引理二

如果字母图中存在一条长度为 $d$ 的路径，路径起点字母出现在 $A$ 的名字中，路径终点字母出现在 $B$ 的名字中，那么存在一条长度为 $d+2$ 的友谊链连接 $A$ 和 $B$。

证明

设字母路径为

$$c_0\rightarrow c_1\rightarrow\cdots\rightarrow c_d. $$

字母图中的每条边 $c_{i-1}\leftrightarrow c_i$ 都来自某个人的名字。也就是说，存在一个人 $P_i$，他的名字中同时包含这两个字母。

因此：

• $A$ 与 $P_1$ 都包含 $c_0$；
• $P_i$ 与 $P_{i+1}$ 都包含 $c_i$；
• $P_d$ 与 $B$ 都包含 $c_d$。

所以

$$A\rightarrow P_1\rightarrow\cdots\rightarrow P_d\rightarrow B $$

是一条合法友谊链，共包含 $d+2$ 个人。引理得证。

定理

算法输出的是每次询问的最短友谊链长度。

证明

根据引理一，任意一条长度为 $k$ 的友谊链都对应一条长度为 $k-2$ 的字母路径。因此，最短友谊链长度不会小于所有合法字母路径长度的最小值加 $2$。

根据引理二，任意一条合法字母路径都能够构造出一条长度为路径长度加 $2$ 的友谊链。因此，所有合法字母路径的最小长度加 $2$ 一定可以实现。

算法通过 Floyd 求出了任意两个字母之间的最短距离，并枚举了起点名字和终点名字中的所有字母组合，所以得到的正是所有合法字母路径中的最短长度。

因此，算法输出的答案等于最短友谊链长度。定理得证。

实现细节与易错点

1. 同一个名字中，一个字母可能出现多次。建图时只需记录该字母是否出现，不需要保留重复次数。
2. 字母图是无向图。同一个名字中的字母两两之间都可以互相转换。
3. 对角线距离必须保持为 $0$。虽然两两连边时可能把同一字母设置为 $1$，但代码中应保证 $d_{i,i}=0$。
4. 不能只连接名字中的相邻字母。只要两个字母出现在同一个名字中，就应该连边。
5. 友谊链长度统计的是人数，不是边数，所以字母最短距离需要加 $2$。
6. 如果字母之间不可达，必须输出 $-1$。
7. 每个测试用例都需要重新初始化距离数组和预处理数组。

参考实现

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

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

    int t;
    cin >> t;

    const int inf = 1e9;

    for(int tc = 1; tc <= t; tc++) {
        int n, q;
        cin >> n >> q;

        vector<string> s(n);
        vector<vector<int>> v(n);
        int d[26][26];

        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < 26; j++) {
                d[i][j] = (i == j ? 0 : inf);
            }
        }

        for(int i = 0; i < n; i++) {
            cin >> s[i];

            bool z[26] = {};

            for(char c : s[i]) {
                z[c - 'A'] = 1;
            }

            for(int c = 0; c < 26; c++) {
                if(z[c]) {
                    v[i].push_back(c);
                }
            }

            for(int x : v[i]) {
                for(int y : v[i]) {
                    if(x != y) {
                        d[x][y] = 1;
                    }
                }
            }
        }

        for(int k = 0; k < 26; k++) {
            for(int i = 0; i < 26; i++) {
                for(int j = 0; j < 26; j++) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }

        vector<array<int, 26>> f(n);

        for(int i = 0; i < n; i++) {
            for(int c = 0; c < 26; c++) {
                f[i][c] = inf;

                for(int x : v[i]) {
                    f[i][c] = min(f[i][c], d[x][c]);
                }
            }
        }

        cout << "Case #" << tc << ":";

        while(q--) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;

            int an = inf;

            for(int c : v[y]) {
                an = min(an, f[x][c]);
            }

            if(an == inf) {
                cout << " -1";
            } else {
                cout << ' ' << an + 2;
            }
        }

        cout << '\n';
    }

    return 0;
}

复杂度分析

设名字的最大长度为 $L$，本题中 $L\le 20$。

处理每个名字中的字母对需要 $O(L^2)$ 时间，所以建立字母图的总时间复杂度为

$$O(NL^2).$$

Floyd 算法在 $26$ 个字母节点上运行，时间复杂度为

$$O(26^3).$$

预处理每个人到每个字母的最短距离，需要枚举 $26$ 个目标字母和名字中的至多 $L$ 个字母，时间复杂度为

$$O(26NL).$$

每次询问最多枚举终点名字中的 $L$ 个字母，因此全部询问的时间复杂度为

$$O(QL).$$

总时间复杂度为

$$O(NL^2+26^3+26NL+QL).$$

由于 $L\le 20$，字母数量固定为 $26$，所以整体复杂度可以近似看作

$$O(N+Q).$$

保存每个人名字中的字母集合和预处理数组需要

$$O(NL+26N)$$

空间，因此总空间复杂度为

$$O(26N+NL).$$