競プロ初中級者100問

ABC065D - Built?

この記事で使うアルゴリズム

プリム法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc065/tasks/arc076_b

この問題は最小全域木を求めることで解くことができます。最小全域技の基本を理解するためにはまず下記の問題に取り組むことをオススメします。

GRL2A Minimum Spanning Tree

方針

解説PDFを参考にすると良いでしょう。

  • 最大でN=10**5であるため、愚直に最小全域木を求めることができません。
  • 街と街の間にコストmin(|a-c|,|b-d|)の辺があるのではなく、コスト|a-c|の辺とコスト|b-d|の辺があると考える
  • x,y座標のうちどちらかに着目し、数直線上に街が並んでいると考える。この時、数直線上で隣接している街と街の間の辺さえ考えれば良い。（それらを足し合わせることで、離れている街同士の辺を表現できる）
  • 最後にx座標についての考察で得られた辺の集合と、y座標のそれの和集合（辺の数は2(N-1)本となる）を考え、最小全域木を求めればよい。

コード

プリム法を用いて実装します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import heapq
N = int(input())
X = [] # ソートするためのリスト
Y = []
for n in range(N):
    x, y = map(int,input().split())
    X.append((x, n)) # 座標と街番号
    Y.append((y, n))
X.sort() # 座標でソート
Y.sort()
adj = [ [] for v in range(N)]
for n in range(N-1): # 数直線上で隣接している街と街の座標の差分を求める
    cost = X[n+1][0] - X[n][0] # まずはx
    adj[X[n+1][1]].append((cost, X[n][1])) # (辺のコスト, to街番号)
    adj[X[n][1]].append((cost, X[n+1][1]))
    cost = Y[n+1][0] - Y[n][0] # yも同様
    adj[Y[n+1][1]].append((cost, Y[n][1]))
    adj[Y[n][1]].append((cost, Y[n+1][1]))

visited = [0] * N # 訪問フラグ
pq = [] # 優先度付きキュー
for w, t in adj[0]: # 始点はどこでも良いので、0とする
    heapq.heappush(pq, (w, t))
visited[0] = 1 # 始点の訪問フラグを立てる

ans = 0
while(pq): # 訪問済みならスキップ
    w, t = heapq.heappop(pq)
    if visited[t]:
        continue
    visited[t] = 1 # 訪問フラグを立てる
    ans += w # スコアに加算
    for w, s in adj[t]: # 隣接する頂点を列挙
        if visited[s]==0: # 未訪問なら探索候補としてpqに追加
            heapq.heappush(pq, (w, s))
print (ans)

記事情報

  • 投稿日：2020年4月28日
  • 最終更新日：2020年5月8日