[BOJ 2887，蟒蛇]行星隧道

问题链接

boj 2887

分类

图论, 排序, 最小生成树

描述

我很惊讶这个问题距离我第一次遇到这个问题已经过去半年多了，但我认为这个问题值得记录下来，因为它得到了令人满意的解决，这与我最近对白金问题的忽视相比是一个很好的改变。

要正式解决这个问题，可以使用联合查找 + 克鲁斯卡尔算法的组合，即从最多 100,000 个坐标中挑选两个坐标，将它们的值从小到大列出，然后将最小的主干线包括在内。

但是，这将导致求解时间为 10⁵ * 10⁵，即大约 100 亿例，这将需要大约 100 秒的求解时间，因此这是一种不可行的求解方法。

提示：如果考虑每 1 亿次操作耗时 1 秒，则很容易计算！

因此，这个问题的关键在于如何将案例数从 O(N²) 减少到 O(N)。

总之，在当前问题中，为任意点构建生成树时，我们不需要考虑相邻点以外的其他点。

假设我们有任意点 A、B，需要将它们连接到一个点 C。

如果 x 值之差（|X_A - X_B|）是小于 y 的最小值，则 z → 假设点 C 的 x 值位于 A 和 B 的 x 值之间。

如果 |X_A - X_C| + |X_B - X_C|，则差不存在。 任何任意的 |X_A - X_B| 保留 |X_A - X_C| 或 |X_B - X_C| 进一步连接 C 的 |X_A - X_B| 必须大于现有生成树 → 不能作为反例存在。

因此，如果在当前问题的最小生成树中包含一条连接两个任意点的干线，则证明这两个点一定是邻居！

解决这个证明是关键，我认为问题的其余部分与典型的联合查找问题并无太大区别。

***]

补充）在使用 PriorityQueue 而不是 heapq 时，我遇到了超时问题，我找到了这个问题的答案。

[在 python 中，heapq 和 PriorityQueue 有什么区别？

答案是 PriorityQueue 更慢，因为它保证了线程安全。

解决方案代码

# 행성 터널

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

def check_union(union_info: list, now_target: int) -> int:
    """
    해당 노드의 현재 유니온을 조회하는 함수
    """

    if union_info[now_target] == -1:
        union_info[now_target] = now_target

    elif union_info[now_target] != now_target:
        union_info[now_target] = check_union(union_info, union_info[now_target])

    return union_info[now_target]

def make_union(union_info: list, target_1: int, target_2: int) -> None:
    """
    두 점이 같은 유니온인지 확인하고 아니라면 합쳐주는 함수
    """
    union_1 = check_union(union_info, target_1)
    union_2 = check_union(union_info, target_2)

    if union_1 == union_2:
        return True

    else:
        if union_1 > union_2:
            union_info[union_1] = union_2
        else:
            union_info[union_2] = union_1

        return False

planet_number = int(input())
coord_list = []

for i in range(planet_number):
    coord_list.append([i] + list(map(int, input().split())))

cost_queue = []

for i in range(1, 4):
    coord_list.sort(key=lambda x: x[i])
    for j in range(planet_number - 1):
        heappush(
            cost_queue,
            (
                coord_list[j + 1][i] - coord_list[j][i],
                (coord_list[j][0], coord_list[j + 1][0]),
            ),
        )

union_info = [-1 for _ in range(planet_number)]

total_length = 0
line_number = 0

while cost_queue:
    if line_number == planet_number - 1:
        break

    now_length, nodes = heappop(cost_queue)
    node_a, node_b = nodes

    if not make_union(union_info, node_a, node_b):
        total_length += now_length
        line_number += 1

print(total_length)