BOJ 4386コンステレーションの作成

7541 ワード
最短距離 find-union 2021.10.30 MST テキストリンク
https://www.acmicpc.net/problem/4386
時間1秒、メモリ128 MB
input :
  • N (1 ≤ N ≤ 100)
    • 各行
  • n個の星のx、y座標
    • output :
  • の正解を出力します.
    • 、絶対/相対誤差は10-2
    条件:

  • 星座を形成する線は、2つの異なる星を一直線に結ぶ形です.

  • すべての星は星座の上の線を通じて直接または間接的に接続しなければならない.

  • 星座を作成する最低コスト、すなわち2つの星間の距離.
    • 質問条件の2,3文目からMSTを確認することが分かる.

    容量


    問題の制限容量は128 MBです.すべてのedgeを保存する場合は、最大99*100個のedgeしか保存できません.
    バイトに変えると99*100*4ですが、128 MBより小さいので全て確認できます.

    n/a.時間


    時間制限の場合でも20万回繰り返すことが可能です.
    だから私は完全に探求する方法を選んだ.
  • のすべてのノードを確認し、可能なedgeを作成します.
  • 最短距離の2つのノードから探索を開始し,親ノードを同じにする.
  • ansを記録し続け、接続されたノードに接続しないでください.
    それ以外にfind、unionを使う以外に、他の内容はないようです.
    • from heapq import heappop, heappush
import sys
import math

def find(node):
    if parent[node] == node:
        return parent[node]
    return find(parent[node])

def union(a, b):
    parent_a = find(a)
    parent_b = find(b)

    if parent_a < parent_b:
        parent[parent_b] = parent_a
    else:
        parent[parent_a] = parent_b

n = int(sys.stdin.readline())
data = []
edge = []
parent = [i for i in range(n)]
for i in range(n):
    x, y = map(float, sys.stdin.readline().split())

    for j in range(len(data)):
        a, b = data[j]
        heappush(edge, (math.sqrt((a - x) ** 2 + (b - y) ** 2), i, j))

    data.append((x, y))

ans = 0
while edge:
    val, a, b = heappop(edge)
    temp_a = find(a)
    temp_b = find(b)

    if temp_a == temp_b:
        continue

    union(a, b)
    ans += val

print(ans)
    [BOJ/C+]#1946新入社員
    [BOJ 10282]ハッカー(Java)