51nod 1212 无向图最小生成树

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

输出样例

这个题我在博客园上写了关于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())

最后，算法是无语言差异的，在各个编程语言中，算法思维是相通的，编程语言只是一个工具而已。这个是我的想法，笑哭

51nod 1212 无向图最小生成树

python3代码：（并查集优化的Kruskal算法）

Python3代码（Prim算法）：

推荐阅读更多精彩内容