N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。
输入
- 第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)
输出
- 输出最小生成树的所有边的权值之和。
输入样例
- 9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8
输出样例
- 37
这个题我在博客园上写了关于C++的题解:https://www.cnblogs.com/Weixu-Liu/p/10901169.html
不过，我在这个写的是python3题解。
嗯，怎么说的，用python3写oj题还是需要多多练习，才能得心应手。
python3代码：（并查集优化的Kruskal算法）
def find(x):
while x != father[x]:
father[x] = find(father[x])
x = father[x]
return x
def merge(a, b):
ax = find(a)
bx = find(b)
if ax == bx:
return 0
else:
father[bx] = ax
return 1
n, m = map(int, input().split())
father, edge, ans = [i for i in range(n + 1)], [], 0
for i in range(m):
u, v, w = map(int, input().split())
edge.append((u, v, w))
edge.sort(key=lambda e: e[2])
for e in edge:
if merge(e[0], e[1]) == 1:
ans += e[2]
print(ans)
Python3代码（Prim算法）：
def Prim(n, u0, mp):
flag[u0] = True
for i in range(1, n + 1):
if i != u0:
lowcost[i] = mp[u0][i]
for i in range(1, n + 1):
temp, t = INF, u0
for j in range(1, n + 1):
if not flag[j] and lowcost[j] < temp:
t = j
temp = lowcost[j]
if t == u0: break
flag[t] = True
for j in range(1, n + 1):
if not flag[j] and lowcost[j] > mp[t][j]:
lowcost[j] = mp[t][j]
if __name__ == '__main__':
n, m = map(int, input().split())
maxn = 1002
INF = 0x3f3f3f3f
mp, lowcost, flag = [[INF for i in range(maxn)] for j in range(maxn)], [0 for i in range(maxn)], [False for i in
range(maxn)]
for _ in range(m):
S, E, W = map(int, input().split())
mp[S][E] = mp[E][S] = W
Prim(n, 1, mp)
ans = 0
for i in lowcost:
ans += i
print(ans)
其中，需要注意的是输入的一系列数字，可以用map(int, input().split())
最后，算法是无语言差异的，在各个编程语言中，算法思维是相通的，编程语言只是一个工具而已。这个是我的想法，笑哭
