1140. 最短网络
摘要
Title: 1140. 最短网络
Tag: kruskal、最小生成树
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1140. 最短网络
-
题意
农夫约翰被选为他们镇的镇长！
他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。
约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。
约翰的农场的编号是1，其他农场的编号是 2∼n。
为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。
你将得到一份各农场之间连接距离的列表，你必须找出能连接所有农场并使所用光纤最短的方案。 -
思路
Kruskal板子题
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50'''
Author: NEFU AB-IN
Date: 2022-03-03 20:43:36
FilePath: \ACM\Acwing\1140.py
LastEditTime: 2022-03-03 20:43:37
'''
N = 110
class Edge():
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
def __lt__(self, t):
return self.w < t.w
g = [[0] * N for _ in range(N)]
fa = [i for i in range(N)]
def find(x):
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
n = int(input())
for i in range(1, n + 1):
g[i][1:] = map(int, input().split())
lst = []
for i in range(1, n + 1):
for j in range(1, n + 1):
lst.append(Edge(i, j, g[i][j]))
lst.sort()
res, cnt = 0, 0
for i in range(len(lst)):
u, v, w = lst[i].u, lst[i].v, lst[i].w
u = find(u)
v = find(v)
if u != v:
fa[u] = v
cnt += 1
res += w
print(res)