結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2020-08-04 23:24:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 487 ms / 2,000 ms |
コード長 | 1,390 bytes |
コンパイル時間 | 275 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 98,520 KB |
最終ジャッジ日時 | 2024-09-14 23:05:27 |
合計ジャッジ時間 | 7,938 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import sys; input = sys.stdin.buffer.readlinesys.setrecursionlimit(10**7)from collections import defaultdictcon = 10 ** 9 + 7; INF = float("inf")def getlist():return list(map(int, input().split()))class UnionFind:def __init__(self, N):self.par = [i for i in range(N)]self.rank = [0] * Ndef find(self, x):if self.par[x] == x:return xelse:self.par[x] = self.find(self.par[x])return self.par[x]def same_check(self, x, y):return self.find(x) == self.find(y)def union(self, x, y):x = self.find(x); y = self.find(y)if self.rank[x] < self.rank[y]:self.par[x] = yelse:self.par[y] = xif self.rank[x] == self.rank[y]:self.rank[x] += 1class Kruskal:def __init__(self, E, N, M, UF, cost):self.uf = UFself.cost = costfor w, u, v, itr in E:if self.uf.same_check(u, v) != True:self.uf.union(u, v)self.cost += wdef mincost(self):return self.cost#処理内容def main():N, M, K = getlist()E = []totalcost = 0for i in range(M):a, b, c = getlist()a -= 1; b -= 1totalcost += cE.append((c, a, b, i))UF = UnionFind(N)cost = 0for i in range(K):e = int(input())e -= 1c, a, b, itr = E[e]UF.union(a, b)cost += cE.sort(key = lambda x:x[0])K = Kruskal(E, N, M, UF, cost)finalcost = K.mincost()print(totalcost - finalcost)if __name__ == '__main__':main()