还是畅通工程

[编程题]还是畅通工程

热度指数：14495 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入描述:

    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
    当N为0时，输入结束，该用例不被处理。

输出描述:

    对每个测试用例，在1行里输出最小的公路总长度。

示例1

输入

输出

3
5

算法知识视频讲解

Python

lx的流星

while True:
    try:
        n=int(input().strip())
        def isroot(i,tree):
            if tree[i]==-1:
                return i
            else:
                temp=isroot(tree[i],tree)
                tree[i]=temp
                return temp 
        if n!=0:
            tree=[-1]*n
            road=[]
            result=0
            #print(istoot(2))
            for i in range(n*(n-1)//2):
                road.append(list(map(int,input().strip().split(' '))))
            #print(road)
            road=sorted(road,key=lambda x:x[2])
            for i in range(n*(n-1)//2):
                one=isroot(road[i][0]-1,tree)
                two=isroot(road[i][1]-1,tree)
                if one!=two:
                    result+=road[i][2]
                    tree[one]=two
            print(result)     
    except:
        break

编辑于 2019-08-05 15:57:25 回复(0)

Python

TimeMac

#最小生成树Python写法，Kruskal算法
#(把所有点集放在一颗树上就相当于全部点连通；从最小权值构建树开始)
def findRoot(x):         #找树根，如果起始树根为自己
    global tree
    if (tree[x] == -1):
        return x
    else:
        temp = findRoot(tree[x])    
        tree[x] = temp
        return temp

try:
    while True:
        num = int(input())
        if num == 0:
            break
        roadsList = []
        for i in range(num * (num - 1) // 2):
            roadsList.append(list(map(int, input().split())))
        roadsList.sort(key=lambda x: x[2])   #Python中list排序可以指定第几号元素排
        tree = [-1 for i in range(num + 1)]  #初始化树，起始树根都为自己
        result = 0
        for i in range(num * (num - 1) // 2): #循环每条路
            a = findRoot(roadsList[i][0])    #查找路的两端的树根
            b = findRoot(roadsList[i][1])
            if a!=b:                         #如果树根相等说明在同一颗树上
                result += roadsList[i][2]    #因为从最小权值开始，所以得到的是最小生成树
                tree[a] = b          
        print(result)
except Exception:
    pass

编辑于 2018-09-20 14:16:15 回复(0)