"国王的烦恼 蓝桥杯校赛 C++"
题目描述的"国王的烦恼"是一个典型的图论问题，涉及到图的连通性与并查集（Disjoint Set）数据结构。在这个问题中，C国的n个岛屿通过m座大桥连接，每座桥都有一定的使用寿命t天。当某座桥不能再使用时，如果两个原本可以通过这座桥或其他桥相连的岛屿变得无法直接或间接到达，即它们分属不同的连通分量，那么就会引发居民的抗议。国王需要知道会有多少天出现这种情况。
输入格式要求读取两个整数n和m，分别代表岛屿数量和桥的数量，以及m行的三个整数a、b和t，分别表示桥连接的两个岛屿编号和使用寿命。输出应为一个整数，表示总共会有多少天出现抗议。
样例解释了如何计算抗议的天数。在样例中，第一天没有桥损坏，所以没有抗议。第二天，连接岛屿2和3的桥不能使用，但不影响其他岛屿间的连通性。第三天，连接岛屿1和2以及1和3的桥同时不能使用，导致岛屿1和2、3分隔开，引发了抗议。同理，第四天，连接岛屿3和4的桥失效，岛屿3和4分隔开，再次引起抗议。因此，总共有2天会出现抗议。
解题的关键在于有效地判断两个岛屿是否仍能通过其他桥相连。这通常使用并查集数据结构来实现。并查集的主要操作包括：
1. `find(x)`: 查找元素x所在的集合的代表元素（根节点），用于确定元素属于哪个集合。
2. `union(x, y)`: 将元素x和y所在的集合合并成一个集合，保持集合的树结构尽可能地平衡，以减少查找和合并的时间复杂度。
给定的代码片段中，`get_parent(data, k)`函数是用于获取数组data中下标k的父节点的，这里的`____(K-1)/2___________`应该填入适当的表达式，通常是在C++中用`(k - 1) / 2`来获取父节点的下标。这个函数的实现依赖于并查集的路径压缩优化策略，它可以在查找过程中将子节点直接指向根节点，从而减少后续查找的深度。
为了正确解决这个问题，我们需要实现以下步骤：
1. 初始化并查集，每个岛屿作为一个独立的集合。
2. 遍历每座桥，根据使用寿命t，在第t+1天将桥从图中移除。
3. 在每天结束时，检查每对岛屿是否仍能互相到达，若不能，则计数加一。
4. 输出总抗议天数。
注意，题目对时间复杂度和内存消耗有要求，因此在实现时需要考虑效率，如使用路径压缩的并查集可以降低查找和合并的时间复杂度。此外，代码需遵循ANSI C/ANSI C++标准，并且只包含必要的库函数，避免依赖特定编译环境或操作系统的特性。最后，`main`函数的返回值应为0，表示程序正常结束。
我的内容管理
展开
