結果
問題 | No.1639 最小通信路 |
ユーザー |
![]() |
提出日時 | 2021-08-06 22:05:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 1,515 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,580 KB |
実行使用メモリ | 79,348 KB |
最終ジャッジ日時 | 2024-09-17 02:04:56 |
合計ジャッジ時間 | 7,531 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
n = int(input()) class UnionFind: # あり本実装 # rankとrootの配列を1つで賄う方法 def __init__(self, n): self.n = n self.par = [-1] * n # 根を求める def find(self, x): if self.par[x] < 0: return x else: self.par[x] = self.find(self.par[x]) return self.par[x] # 同じかどうかの判定 def is_same(self, x, y): return self.find(x) == self.find(y) # 集合の大きさ def size(self, x): return -self.par[self.find(x)] # 2つの集合の合体 # 重みが大きい方に小さい方をつけるようにする def unite(self, x, y): x = self.find(x) y = self.find(y) if x == y: return False if self.par[x] > self.par[y]: x, y = y, x self.par[x] += self.par[y] self.par[y] = x return True num = (n * (n - 1)) // 2 ans = 0 ABC = [list(map(int, input().split())) for _ in range(num)] ABC.sort(key=lambda x: x[2]) ok = 10 ** 100 + 10 ng = 0 def check(mid): UF = UnionFind(n) cnt = 1 for i in range(num): a, b, c = ABC[i] a, b = a - 1, b - 1 if c > mid: break if UF.is_same(a, b): continue UF.unite(a, b) cnt += 1 if cnt == n: return 1 return 0 while ok - ng > 1: mid = (ok + ng) // 2 if check(mid): ok = mid else: ng = mid print(ok)