F. Royal Questions - 题解

比赛与标签

比赛: Codeforces Round 441 (Div. 1, by Moscow Team Olympiad) 标签: dsu, graphs, greedy, *2500 难度: *2500

题目大意喵~

在一个古老的王国里，有 n 位王子和 m 位公主。每一位公主 i 都有两位心仪的王子人选，分别是 a_i 和 b_i，并且她会带来 w_i 的嫁妆。

国王的目标是安排一些婚姻，使得国库收入的总嫁妆最多。当然啦，婚姻要遵循一些基本法，那就是：

一位王子最多只能娶一位公主。
一位公主最多也只能嫁给一位王子。
公主只会嫁给她心仪的两位王子之一。

我们需要计算出，国王最多能获得多少金币呢？

解题思路喵~

主人 sama，看到“最大化总嫁妆”这样的字眼，是不是立刻就想到了贪心呢？喵~ 没错！这种最优化问题，贪心往往是一条非常有效的思路。我们的直觉是：嫁妆越多的公主，我们越应该优先考虑她！

第一步：把问题变成图的样子

让我们来施展一点魔法，把这个问题变得更直观一些。我们可以把 n 位王子看作是图上的 n 个节点（vertices）。而每一位公主呢，她连接了她心仪的两位王子，这不就是一条**边（edge）嘛！这条边的权重（weight）**就是她的嫁妆 w。

这样一来，问题就转化成：在一个有 n 个节点和 m 条带权边的图上，我们要选择一个边的子集，使得它们的权重之和最大。同时，这个选择必须满足婚姻的约束条件。

第二步：分析婚姻约束

“一位王子最多娶一位公主”，在我们的图模型里意味着什么呢？这意味着每个节点最多只能与一条被选中的边相关联。

一个图，如果其中所有节点的度数（连接的边数）都不超过 1，那它一定是由一堆互不相干的边组成的。这就是图论中的匹配（Matching）！所以，我们的目标其实是求这个图的最大权匹配（Maximum Weight Matching）。

但是！最大权匹配的通用算法（比如“带花树算法”）非常复杂，而且这道题的数据量（n, m 高达 200,000）也告诉我们，肯定有更简单、更高效的解法。这就要回到我们最初的贪心思路了！

第三步：Kruskal 算法的奇妙变身

我们按照嫁妆从高到低的顺序来考虑每一位公主（也就是每一条边）。这个“按权重排序，依次处理”的流程，是不是和求最大生成树的 Kruskal 算法很像？喵~ 让我们顺着这个思路探索一下。

我们会使用**并查集（Disjoint Set Union, DSU）**来维护王子们所在的连通分量（可以理解为“朋友圈”）。

当我们考虑一位嫁妆为 w、心仪王子为 u 和 v 的公主时：

如果 u 和 v 不在同一个朋友圈（连通分量）里：
- 这意味着我们可以通过这位公主，将两个原本不相干的朋友圈连接起来。
- 在形成一个树形结构（没有环）的朋友圈里，若有 k 个王子，我们最多可以安排 k-1 场婚姻（k-1 条边），这样总会有一个王子单身，可以作为“对外联络员”。
- 所以，只要两个朋友圈中至少有一个是树形结构（没有“满员”），我们就可以通过它们各自的“单身王子”来建立这场新的婚姻。
- 我们怎么判断一个朋友圈是否“满员”了呢？我们稍后揭晓！
如果 u 和 v 已经在同一个朋友圈里：
- 如果我们接受这位公主，那么在她所在的这个朋友圈里，就会形成一个环！
- 形成环意味着什么呢？一个有 k 个王子的树形朋友圈，有 k-1 场婚姻。现在多了一场，变成了 k 场婚姻。这 k 位王子，刚好可以和 k 位公主两两配对，全部成功脱单！这个朋友圈就“满员”了，再也容不下任何新的婚姻关系了。
- 所以，如果这个朋友圈之前还没有形成环，我们就可以接受这位公主，让她来完成“闭环”的壮举！

最终的贪心策略

结合上面的分析，我们的完美策略就诞生啦！

对并查集进行扩展：除了记录父节点，我们还需要一个布尔数组 is_cyclic 来标记每个朋友圈（连通分量）是否已经“满员”（形成了环）。
将所有公主按嫁妆从高到低排序。
遍历排序后的公主 (u, v, w)：
- 找到 u 和 v 的根节点 root_u 和 root_v。
- 情况一：root_u == root_v (在同一个朋友圈)
  - 如果这个朋友圈还没形成环 (!is_cyclic[root_u])，太棒了！接受这位公主，她的嫁妆 w 我们收下了。然后把这个朋友圈标记为已形成环 (is_cyclic[root_u] = true)。
  - 如果已经有环了，那只能遗憾地拒绝她了，喵~
- 情况二：root_u != root_v (在不同朋友圈)
  - 如果这两个朋友圈至少有一个还没形成环 (!is_cyclic[root_u] || !is_cyclic[root_v])，我们就可以接受这位公主！收下嫁妆 w，然后合并这两个朋友圈。
  - 合并后的新朋友圈是否形成环，取决于原来的两个：只要有一个是环，新的也是环 (is_cyclic[new_root] = is_cyclic[root_u] || is_cyclic[root_v])。
  - 如果两个朋友圈都已经是环了，那就没办法连接它们了，因为没有“单身王子”来当桥梁了。

这个算法本质上是在寻找图的最大权伪森林（Maximum Weight Pseudoforest）。伪森林就是每个连通分量最多只有一个环的图，这恰好完美对应了我们的婚姻约束！是不是很奇妙呀，呐？

代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// 快速 I/O，让程序跑得飞快喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

// 用一个结构体来表示可爱的公主殿下
struct Princess {
    int u, v, w; // 两位心仪的王子 u, v 和她的嫁妆 w
};

// 比较函数，用来给公主们按嫁妆从高到低排队
bool comparePrincesses(const Princess& a, const Princess& b) {
    return a.w > b.w;
}

// 并查集（Disjoint Set Union, DSU）数据结构
// 用来维护王子们的“朋友圈”关系捏~
struct DSU {
    std::vector<int> parent;     // 记录每个节点的父节点
    std::vector<int> sz;         // 记录每个集合的大小（用于按大小合并优化）
    std::vector<bool> is_cyclic; // 记录这个朋友圈是不是已经“满员”了（形成环了）

    // 构造函数，为 n 个王子初始化并查集 (王子编号 1 到 n)
    DSU(int n) {
        parent.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0); // 每个王子一开始都是自己的老大
        sz.assign(n + 1, 1);                        // 每个朋友圈一开始都只有一个人
        is_cyclic.assign(n + 1, false);             // 一开始都还没形成环
    }

    // 查找元素 i 所在集合的代表（根节点），带路径压缩优化
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    // 合并元素 i 和 j 所在的集合，按大小合并
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // 按大小合并的启发式策略，小的合并到大的上面
            if (sz[root_i] < sz[root_j])
                std::swap(root_i, root_j);
            
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            
            // 如果两个朋友圈中的任何一个已经是环，那么合并后的大朋友圈也是环
            is_cyclic[root_i] = is_cyclic[root_i] || is_cyclic[root_j];
        }
    }
};

int main() {
    fast_io();

    int n, m;
    std::cin >> n >> m;

    std::vector<Princess> princesses(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> princesses[i].u >> princesses[i].v >> princesses[i].w;
    }

    // 贪心大法好！先把嫁妆最多的公主殿下请出来~
    std::sort(princesses.begin(), princesses.end(), comparePrincesses);

    DSU dsu(n);
    long long total_dowry = 0;

    // 贪心地处理每一位公主。这相当于 Kruskal 算法求最大权伪森林
    for (const auto& p : princesses) {
        int root_u = dsu.find(p.u);
        int root_v = dsu.find(p.v);

        if (root_u == root_v) {
            // 两位王子已经在同一个朋友圈了
            // 只有当这个朋友圈还没形成环时，我们才能接受这位公主
            // 接受她之后，这个朋友圈就形成环，“满员”啦
            if (!dsu.is_cyclic[root_u]) {
                total_dowry += p.w;
                dsu.is_cyclic[root_u] = true;
            }
        } else {
            // 两位王子在不同的朋友圈
            // 只要两个朋友圈不都是“满员”状态，我们就可以撮合他们
            if (!dsu.is_cyclic[root_u] || !dsu.is_cyclic[root_v]) {
                total_dowry += p.w;
                dsu.unite(p.u, p.v);
            }
        }
    }

    std::cout << total_dowry << std::endl;

    return 0;
}

复杂度分析

时间复杂度: O(m log m) 的说。
- 主要的时间开销在于对 m 位公主进行排序，这是 O(m log m)。
- 之后遍历 m 位公主，对每位公主执行并查集的 find 和 unite 操作。由于使用了路径压缩和按大小合并的优化，单次操作的平均时间复杂度接近常数，记为 α(n)（反阿克曼函数，增长极其缓慢）。所以循环部分是 O(m * α(n))。
- 总的来说，排序是瓶颈，所以总时间复杂度是 O(m log m)。
空间复杂度: O(n + m) 的说。
- 我们需要一个数组来存储 m 位公主的信息，需要 O(m) 的空间。
- 并查集需要几个数组来存储 n 位王子的信息（parent, sz, is_cyclic），需要 O(n) 的空间。
- 所以总空间复杂度是 O(n + m)。

知识点与总结

主人 sama，这道题真是太棒了，让我们来总结一下学到了什么吧！

贪心思想: 面对最优化问题，特别是求最大/最小值时，首先要想想贪心！从最有利的选项开始，往往能找到通往正确答案的捷径。
图论建模: 学会将实际问题抽象成图论模型是成为算法高手的必备技能！王子变节点，公主变带权边，问题瞬间清晰了许多。
并查集 (DSU) 的妙用: 并查集不仅能判断连通性、维护集合，还能通过增加额外信息（如此处的 is_cyclic）来解决更复杂的问题。它是处理动态连通性问题的强大工具。
Kruskal 算法的拓展: 这道题的解法可以看作是 Kruskal 算法的变体。Kruskal 求最大生成树（无环），而我们求最大权伪森林（每个连通分量最多一环）。这告诉我们，经典的算法思想是可以灵活变通和拓展的！

总之，遇到问题不要怕，先从最直观的贪心想法入手，再用合适的模型（如图论）去描述它，最后选择强大的数据结构（如并查集）来实现它，一步一步，问题就迎刃而解啦！主人 sama 又变强了呢，喵~♥

F. Royal Questions - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

代码实现 ​

复杂度分析 ​

知识点与总结 ​