結果
問題 | No.1639 最小通信路 |
ユーザー | MasKoaTS |
提出日時 | 2021-10-03 18:58:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 254 ms / 2,000 ms |
コード長 | 2,765 bytes |
コンパイル時間 | 396 ms |
コンパイル使用メモリ | 86,852 KB |
実行使用メモリ | 84,868 KB |
最終ジャッジ日時 | 2023-09-28 19:16:06 |
合計ジャッジ時間 | 13,823 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 226 ms
83,480 KB |
testcase_01 | AC | 226 ms
83,268 KB |
testcase_02 | AC | 238 ms
84,552 KB |
testcase_03 | AC | 254 ms
84,592 KB |
testcase_04 | AC | 251 ms
84,496 KB |
testcase_05 | AC | 239 ms
84,828 KB |
testcase_06 | AC | 242 ms
84,660 KB |
testcase_07 | AC | 236 ms
83,292 KB |
testcase_08 | AC | 241 ms
84,808 KB |
testcase_09 | AC | 231 ms
83,496 KB |
testcase_10 | AC | 238 ms
83,820 KB |
testcase_11 | AC | 245 ms
84,636 KB |
testcase_12 | AC | 235 ms
83,912 KB |
testcase_13 | AC | 244 ms
84,860 KB |
testcase_14 | AC | 226 ms
83,184 KB |
testcase_15 | AC | 233 ms
83,908 KB |
testcase_16 | AC | 241 ms
84,556 KB |
testcase_17 | AC | 243 ms
84,676 KB |
testcase_18 | AC | 232 ms
83,468 KB |
testcase_19 | AC | 247 ms
84,548 KB |
testcase_20 | AC | 245 ms
84,628 KB |
testcase_21 | AC | 232 ms
83,456 KB |
testcase_22 | AC | 238 ms
83,860 KB |
testcase_23 | AC | 243 ms
84,828 KB |
testcase_24 | AC | 236 ms
83,820 KB |
testcase_25 | AC | 235 ms
83,884 KB |
testcase_26 | AC | 232 ms
83,332 KB |
testcase_27 | AC | 232 ms
83,448 KB |
testcase_28 | AC | 230 ms
83,252 KB |
testcase_29 | AC | 246 ms
84,504 KB |
testcase_30 | AC | 244 ms
84,556 KB |
testcase_31 | AC | 234 ms
83,296 KB |
testcase_32 | AC | 247 ms
84,608 KB |
testcase_33 | AC | 233 ms
83,324 KB |
testcase_34 | AC | 245 ms
84,860 KB |
testcase_35 | AC | 249 ms
84,512 KB |
testcase_36 | AC | 246 ms
84,504 KB |
testcase_37 | AC | 245 ms
84,860 KB |
testcase_38 | AC | 231 ms
83,584 KB |
testcase_39 | AC | 232 ms
83,888 KB |
testcase_40 | AC | 234 ms
83,312 KB |
testcase_41 | AC | 233 ms
83,440 KB |
testcase_42 | AC | 246 ms
84,868 KB |
testcase_43 | AC | 229 ms
83,256 KB |
testcase_44 | AC | 229 ms
83,272 KB |
ソースコード
import itertools as iter import collections as coll import heapq as hq import bisect as bis from decimal import Decimal as dec from copy import deepcopy as dcopy import math import sys sys.setrecursionlimit(10**6) def input(): return sys.stdin.readline().rstrip() def getN(): return int(sys.stdin.readline().rstrip()) def getNs(): return map(int,sys.stdin.readline().rstrip().split()) def getList(): return list(map(int,sys.stdin.readline().rstrip().split())) def strinps(n): return [sys.stdin.readline().rstrip() for _ in range(n)] pi = 3.141592653589793 mod = 10**9+7 MOD = 998244353 INF = math.inf dx = [1,0,-1,0]; dy = [0,1,0,-1] """ Union-Find from : https://github.com/customaddone/beginPython/blob/master/cgi-bin/library/unionfind/unionfind.py ref : https://algo-logic.info/union-find-tree/ """ class UnionFind(): #Uni = UnionFind(n) のようにする def __init__(self, n): self.n = n self.parents = [-1] * n #xの親(親がいないときは自身の番号を返す) def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] #xとyを関係付ける def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x # if x > y: # よりrootのインデックスが小さい方が親 # x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x #xとyが同じ組に属するかどうか def same(self, x, y): return self.find(x) == self.find(y) #xが属する組の大きさ def size(self, x): return -self.parents[self.find(x)] #xが属する組の全要素をリストとして取得 def members(self, x): root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] #Union-Find木の根に当たる要素全てをリストとして取得 def roots(self): return [i for i, x in enumerate(self.parents) if x < 0] #Union-Find木の根とそれに属する組の全要素 def all_group_members(self): return {r: self.members(r) for r in self.roots()} """ クラスカル法によって最小全域木を求める ref : https://algo-logic.info/kruskal-mst/ """ """ (入力例) V, E = map(int,sys.stdin.readline().rstrip().split()) edges = [] for i in range(E): s, t, w = map(int,sys.stdin.readline().rstrip().split()) edges.append((w, s, t)) edges.sort() """ def kruskal(n, edges): U = UnionFind(n) res = 0 for e in edges: w, s, t = e if not U.same(s, t): res = max(res,w) U.union(s, t) return res """ Main Code """ n = getN() e = n*(n-1)//2 edges = [] for i in range(e): s, t, w = map(int,sys.stdin.readline().split()) edges.append((w, s-1, t-1)) edges.sort() print(kruskal(n,edges))