测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。 当N为0时输入结束。
每个测试用例的输出占一行,输出全省畅通需要的最低成本。
3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0
3 1 0
在输入时就对已建好的路进行树的生成,且不保存,而后只保存未开始修建的路,然后进行排序和树的继续生成。
def findRoot(village): global villages if villages[village] == -1: return village else: temp = findRoot(villages[village]) villages[village] = temp return temp while True: try: n = int(input()) if n == 0: break villages = [-1 for i in range(n+1)] nodeNum = 1 roads = [] for i in range(n*(n-1)//2): temp = list(map(int, input().split())) if temp[3] == 1: a = findRoot(temp[0]) b = findRoot(temp[1]) if a != b: villages[a] = b nodeNum += 1 else: roads.append(temp) costs = 0 roads.sort(key=lambda x:x[2]) for i in range(len(roads)): a = findRoot(roads[i][0]) b = findRoot(roads[i][1]) if a != b: villages[a] = b costs += roads[i][2] nodeNum += 1 if nodeNum == n: break print(costs) except Exception: break