import sys N = 101 inf = 0x3f3f3f3f def prim(n, m, mapp): vis = [False] * N dis = [inf] * N sum_val = 0 for i in range(1, n + 1): dis[i] = mapp[1][i] vis[1] = True dis[1] = 0 for i in range(1, n): minn = inf u = 0 for j in range(1, n + 1): if not vis[j] and dis[j] < minn: minn = dis[j] u = j vis[u] = True sum_val += minn for j in range(1, n + 1): if not vis[j] and mapp[u][j] < dis[j]: dis[j] = mapp[u][j] return sum_val if __name__ == '__main__': n, m = map(int, input().split()) mapp = [[inf] * N for _ in range(N)] ss = 0 for _ in range(m): a, b, c = map(int, input().split()) mapp[a][b] = mapp[b][a] = c ss += c result = prim(n, m, mapp) print(ss - result)
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题9.4 (Java代码)浏览:1419 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:546 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:968 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:338 |
【计算球体积】 (C语言代码)浏览:1106 |
用筛法求之N内的素数。 (C语言代码)浏览:669 |
字符逆序 (C语言代码)浏览:460 |
1124题解浏览:595 |
DNA (C语言代码)浏览:395 |
链表数据求和操作 (C语言代码)浏览:952 |