結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2022-12-27 23:27:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 596 ms / 2,000 ms |
コード長 | 2,427 bytes |
コンパイル時間 | 228 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 102,568 KB |
最終ジャッジ日時 | 2024-11-22 10:52:49 |
合計ジャッジ時間 | 8,130 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import sysinput = sys.stdin.readlineclass UnionFind():def __init__(self, n: int) -> None:"""Arguments:n {int} -- 木の全頂点数"""self.par = [-1]*nself.rank = [0]*nself.siz = [1]*ndef root(self, x: int) -> int:"""Arguments:x {int} -- 根を知りたい頂点Return:root(x) {int} -- 入力 x の根にあたる頂点"""if self.par[x] == -1:return xself.par[x] = self.root(self.par[x])return self.par[x]def is_same(self, x: int, y: int) -> bool:"""2頂点が同じグループに属するかを判定Arguments:x, y {int} -- 判定したい2頂点Return:{bool} -- 同じならTrue, 異なるならFalse"""return self.root(x) == self.root(y)def unite(self, x, y) -> bool:"""頂点 x, y を同じグループとして結合既に同じグループなら何もしないArguments:x, y {int} -- 結合したい2頂点Return:{bool} -- 結合したらTrue, 既に同じ場合はFalse"""if self.is_same(x, y):return Falserx = self.root(x)ry = self.root(y)if self.rank[rx] < self.rank[ry]:rx, ry = ry, rxelif self.rank[rx] == self.rank[ry]:self.rank[rx] += 1self.par[ry] = rxself.siz[rx] += self.siz[ry]return Truedef size(self, x) -> int:"""頂点が属するグループの大きさArguments:x {int} -- 大きさを知りたい頂点Return:size(x) {int} -- 頂点 x の属するグループの大きさ"""return self.siz[self.root(x)]n, m, k = map(int, input().split())roads = [tuple(map(int, input().split())) for _ in range(m)]s = set()uf = UnionFind(n+1)cost = 0all_cost = sum(roads[i][2] for i in range(m))for i in range(m):s.add(roads[i])for _ in range(k):e = int(input()) - 1a, b = (roads[e][0], roads[e][1])cost += roads[e][2]s.discard((a, b))uf.unite(a, b)s = sorted(list(s), key=lambda x: x[2])for a, b, c in s:if uf.unite(a, b):cost += cprint(all_cost-cost)