NekoNowcoder

Appearance

Investigating Legions - 题解 ​

标签与难度 ​

标签: 聚类算法, 图论, 贪心, 概率, 启发式算法 难度: 1900

题目大意喵~ ​

各位特工喵，晚上好！这次的任务有点棘手哦~ 我们潜入了A国，截获了一份机密文件。文件记录了A国 nn 支部队两两之间是否属于同一个军团（Legion）的情报。

但是，情报被动了手脚！每一条记录（比如“部队 ii 和部队 jj 是否同属一个军团”）都有 p=S/100p = S/100 的概率被翻转（是的变成不是，不是的变成是）。

我们知道总共有 nn 支部队，也知道这个出错的概率参数 SS，但不知道具体有多少个军团，也不知道每支部队到底属于哪个军团。我们的任务就是，利用这份充满噪声的情报，尽可能准确地还原出每支部队所属的军团编号。

输入会给我们部队数量 nn 和参数 SS，以及一个长长的 01 字符串，它表示了所有部队对 (i,j)(i, j) (其中 i<ji < j) 之间是否属于同一军团的（带噪声的）判断结果。我们要输出一个方案，给每支部队分配一个军团编号（从0开始）。

举个栗子，如果我们判断部队1、2、5属于军团0，部队3、4属于军团1，那么就可以输出 0 1 1 2 2 （欸不对，是 0 1 1 2 0 这样子，喵~）。

解题思路分析 ​

这道题的核心，就像是我在猫抓板上磨爪子，要从一团乱麻中理出线索，喵~ 我们手里的情报是不可靠的，但也不是完全随机的。我们可以利用概率的性质来“去噪”，找到最可能的事实真相。

问题的本质是一个聚类问题。我们要把 nn 个点（部队）分成若干个簇（军团）。同一簇内的点彼此之间关系紧密，不同簇之间的点关系疏远。

让我们来想一想，如果两支部队 u 和 v 真的在同一个军团里，它们的“社交圈”应该是什么样的呢？ 对于任何第三方部队 k：

  1. 如果 k 和 u、v 在同一个军团，那么真实的关系是 (u,k) = 1 且 (v,k) = 1。
  2. 如果 k 在别的军团，那么真实的关系是 (u,k) = 0 且 (v,k) = 0。

也就是说，在没有噪声的理想情况下，同一个军团的两支部队，它们与其他所有部队的关系模式是完全相同的！

现在加入了噪声，这个完美的性质被破坏了。但是，即使有噪声，来自同一军团的部队 u 和 v，它们与其他部队的关系向量（就是那一串0和1）仍然会非常相似。而不同军团的部队，它们的关系向量相似度就会低很多。这就是我们破案的关键线索，喵！

基于这个“社交圈相似”的原理，我们可以设计一个贪心的聚类算法：

  1. 寻找“发起猫”：我们从还没有被分配军团的部队里，随便选一支，比如部队 seed，作为新军团的发起者（或者说是“发起猫”~）。

  2. 定义“朋友圈”：我们把所有和 seed 在情报中被标记为“同一军团”的部队，集合起来，形成一个临时的“朋友圈” C。这个朋友圈 C 是我们对 seed 所在真实军团的一个（带有噪声的）初步猜测。

  3. “摇人”入团：现在，我们要考察其他所有还未分配军团的部队，看看谁有资格加入 seed 的这个新军团。判断标准是什么呢？很简单，就是少数服从多数！ 对于任何一支待考察的部队 candidate，我们去问问 C 里的所有成员：“嘿，你们和 candidate 是不是一伙的呀？”。我们统计一下，C 中有多少成员在情报里显示与 candidate 是同一军团的。 如果这个数量超过了 C 总人数的一半，我们就有理由相信，candidate 和 seed 属于同一个军团。因为 candidate 得到了 seed 朋友圈里“大多数”成员的认可，喵~

  4. 成立新军团：所有通过了上述“投票”的未分配部队（包括 seed 自己），我们就把它们正式划分为一个新的军团。

  5. 重复此过程：不断重复1-4步，直到所有部队都被分配了军团为止。

这个算法就像滚雪球一样，从一个小的 seed 开始，通过朋友圈投票，把所有志同道合的伙伴都拉进来，形成一个大雪球（军团），然后继续找下一个 seed 滚下一个雪球。

让我们用一个简单的例子来感受一下： 假设 seed 是部队1，它的朋友圈 C = {1, 3, 4, 7}。现在我们要判断部队5是否应该加入。我们就去检查 g[5][1], g[5][3], g[5][4], g[5][7]。如果其中有3个或4个是 1，那么 3 > |C|/2 = 4/2 = 2，我们就认为部队5应该加入。反之，如果只有0个或1个是 1，那它可能就是“道不同不相为谋”啦。

这种基于邻居相似度的启发式贪心策略，虽然不保证能找到绝对完美的解，但在这类问题中通常表现得相当不错，而且足以通过本题的数据，喵~

代码实现 ​

好啦，思路清晰了，就让我来把这个过程用代码实现出来吧！看好咯~

cpp
#include <iostream>
#include <vector>
#include <string>
#include <numeric>

const int MAXN = 305;

// g[i][j] = true 表示情报中 i 和 j 属于同一军团
bool g[MAXN][MAXN];
// legion_id[i] 存储部队 i 被分配到的军团编号
int legion_id[MAXN];

void solve() {
    int n, s;
    std::cin >> n >> s;

    // 读取并解析输入的01字符串，构建邻接矩阵
    std::string relationships;
    // 由于输入可能没有空格，一次性读完所有关系
    if (n > 0) {
        std::string line;
        // C++ 的 cin 在读取 n 和 s 后，会留下一个换行符在缓冲区。
        // 如果不处理，下一个 getline 或类似的读整行的操作会立即结束。
        // std::ws 会丢弃前导的空白字符，包括换行符。
        std::cin >> std::ws; 
        std::getline(std::cin, line);
        relationships += line;
        // 如果关系字符串太长，可能分多行，需要继续读
        while (relationships.length() < n * (n - 1) / 2) {
            std::getline(std::cin, line);
            relationships += line;
        }
    }

    int rel_idx = 0;
    for (int i = 1; i <= n; ++i) {
        g[i][i] = true; // 自己和自己当然是同一个军团
        for (int j = i + 1; j <= n; ++j) {
            g[i][j] = g[j][i] = (relationships[rel_idx++] == '1');
        }
    }

    // 初始化所有部队为未分配状态（-1）
    for (int i = 1; i <= n; ++i) {
        legion_id[i] = -1;
    }

    int current_legion_idx = 0;
    for (int i = 1; i <= n; ++i) {
        // 如果当前部队已经被分配了军团，就跳过
        if (legion_id[i] != -1) {
            continue;
        }

        // 选 i 作为新军团的 "seed"
        // 1. 找到 seed 的朋友圈
        std::vector<int> seed_friends;
        for (int j = 1; j <= n; ++j) {
            if (g[i][j]) {
                seed_friends.push_back(j);
            }
        }

        // 2. 遍历所有未分配的部队，看谁能加入这个新军团
        for (int k = 1; k <= n; ++k) {
            if (legion_id[k] != -1) {
                continue;
            }

            int agreement_count = 0;
            for (int friend_of_seed : seed_friends) {
                if (g[k][friend_of_seed]) {
                    agreement_count++;
                }
            }

            // 核心判断：如果与朋友圈中超过一半的成员是朋友，就吸纳进来
            // 使用 a * 2 > b 的形式避免浮点数除法带来的精度问题
            if (agreement_count * 2 > seed_friends.size()) {
                legion_id[k] = current_legion_idx;
            }
        }
        current_legion_idx++;
    }

    // 输出结果
    for (int i = 1; i <= n; ++i) {
        std::cout << legion_id[i] << (i == n ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N3)O(N^3) 我们的代码主体有三层循环嵌套的结构。

    1. 最外层循环 for (int i = 1; i <= n; ++i) 负责寻找未分配的部队作为 seed。在最坏的情况下（比如每个部队自成一个军团），这个循环会完整执行 NN 次。
    2. 中间的循环 for (int k = 1; k <= n; ++k) 遍历所有部队，以判断它们是否能加入当前 seed 正在组建的军团。这层是 O(N)O(N)。
    3. 最内层的循环 for (int friend_of_seed : seed_friends) 计算 k 与 seed 朋友圈的“契合度”。seed_friends 的大小最坏情况下是 O(N)O(N)。 所以总的时间复杂度是 O(N×N×N)=O(N3)O(N \times N \times N) = O(N^3)。对于 N=300N=300 的数据规模，3003=2.7×107300^3 = 2.7 \times 10^7，这个计算量是在可接受范围内的，可以通过！

  • 空间复杂度: O(N2)O(N^2) 我们使用了几个主要的存储空间：

    1. bool g[MAXN][MAXN]：这是一个邻接矩阵，用来存储部队间的关系，大小为 O(N2)O(N^2)。
    2. int legion_id[MAXN]：存储每支部队的军团归属，大小为 O(N)O(N)。
    3. std::vector<int> seed_friends：在循环中临时存储 seed 的朋友圈，大小最多为 O(N)O(N)。 因此，占主导地位的是邻接矩阵，总空间复杂度为 O(N2)O(N^2)。

知识点总结 ​

这道题虽然包装在特工故事里，但考察的是非常实用的算法思想，喵~

  1. 启发式算法 (Heuristics)：当一个问题没有已知的、能在多项式时间内解决的最优算法时（或者最优算法太复杂），我们可以设计一种基于直觉或经验的规则（即启发式规则）来寻找一个足够好的近似解。本题的“朋友圈多数票决”就是一种非常有效的启发式规则。

  2. 贪心算法 (Greedy Algorithm)：我们的解法是贪心的。每一步都为一支部队或一批部队做出“局部最优”的决策（即把它分给当前看起来最合适的军团），并且一旦分配，就不再更改。

  3. 聚类思想 (Clustering)：这是数据科学和机器学习中的一个基本概念。其目标是将数据点分组，使得同一组内的数据点相似度高，而不同组的数据点相似度低。本题就是对图节点进行聚类。

  4. 图的邻接矩阵表示：对于需要频繁查询任意两点间是否存在边的场景（比如本题的投票过程），使用邻接矩阵进行图的存储是非常高效的，查询时间是 O(1)O(1)。

希望这篇题解能帮到你，让你对处理带噪声数据和聚类问题更有信心！如果还有不明白的地方，随时可以再来问我哦，喵~