[已解决]求助 Python 最小生成树

欧德奈瑞

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

输入格式:
有多组测试数据，每组数据请依次输入图中各顶点的值，每个顶点值以回车间隔，并以#作为输入结束符；再请依次输入图中每条边的两个顶点值，两个顶点值以空格作为间隔，每输入一组后进行换行，仍以#结束输入；最后一行为某顶点v。

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

输出格式:
对每个测试用例，在1行里输出最小的公路总长度，如果未能找到请输出"no found!"。

输入样例:
在这里给出两组输入。例如：

1. 3 3
   
2. 1 2 10
   
3. 1 3 20
   
4. 2 3 40
   
5. 4 6
   
6. 1 2 10
   
7. 1 3 40
   
8. 1 4 10
   
9. 2 3 30
   
10. 2 4 20
    
11. 3 4 50
    
12. 0 0
    
13. #

复制代码

输出样例:
在这里给出相应的输出。例如：

1. 30
   
2. 50

复制代码

最佳答案

月排行榜 / 总排行榜

逃兵

2020-12-12 15:19:19

1. def tempfun(x,y):
   
2.     if x > y:
   
3.         return (y,x)
   
4.     else:
   
5.         return (x,y)
   
6. temp = 0
   
7. lst=[]
   
8. lst2=[]
   
9. while temp != '#':
   
10.     temp=input()
    
11.     lst +=[temp]
    
12. 
    
13. for i in range(len(lst)):
    
14.     if lst[i].count(' ') == 1:
    
15.         lst2.append(lst[i+1:i+int(lst[i][-1])+1])
    
16. lst2=lst2[:-1]
    
17. for i in lst2:
    
18.     try:
    
19.         dic={}
    
20.         for j in i:
    
21.             lstj=j.split()
    
22.             x = int(lstj[0])
    
23.             y = int(lstj[1])
    
24.             z = int(lstj[2])
    
25.             dic[(x,y)]=z
    
26.         long=[]
    
27.         for cell in dic:
    
28.             temp=[]
    
29.             for num in range(1,max(dic.keys())[1]+1):
    
30.                 if num != cell[0] and num != cell[1]:
    
31.                     temp.append(dic[tempfun(cell[0],num)]+dic[tempfun(cell[1],num)])
    
32.             temp.append(dic[cell])
    
33.             m = min(temp)
    
34.             long.append(m)
    
35. 
    
36.         print(max(long))
    
37.     except:
    
38.         print('no found!')
    

复制代码

跳转到最佳答案楼层

逃兵

1. def tempfun(x,y):
   
2.     if x > y:
   
3.         return (y,x)
   
4.     else:
   
5.         return (x,y)
   
6. temp = 0
   
7. lst=[]
   
8. lst2=[]
   
9. while temp != '#':
   
10.     temp=input()
    
11.     lst +=[temp]
    
12. 
    
13. for i in range(len(lst)):
    
14.     if lst[i].count(' ') == 1:
    
15.         lst2.append(lst[i+1:i+int(lst[i][-1])+1])
    
16. lst2=lst2[:-1]
    
17. for i in lst2:
    
18.     try:
    
19.         dic={}
    
20.         for j in i:
    
21.             lstj=j.split()
    
22.             x = int(lstj[0])
    
23.             y = int(lstj[1])
    
24.             z = int(lstj[2])
    
25.             dic[(x,y)]=z
    
26.         long=[]
    
27.         for cell in dic:
    
28.             temp=[]
    
29.             for num in range(1,max(dic.keys())[1]+1):
    
30.                 if num != cell[0] and num != cell[1]:
    
31.                     temp.append(dic[tempfun(cell[0],num)]+dic[tempfun(cell[1],num)])
    
32.             temp.append(dic[cell])
    
33.             m = min(temp)
    
34.             long.append(m)
    
35. 
    
36.         print(max(long))
    
37.     except:
    
38.         print('no found!')
    

复制代码

欧德奈瑞

逃兵 发表于 2020-12-12 15:19

1. 3 2
   
2. 1 2 10
   
3. 2 3 40
   
4. 4 6
   
5. 1 2 10
   
6. 1 3 40
   
7. 1 4 10
   
8. 2 3 30
   
9. 2 4 20
   
10. 3 4 50
    
11. 0 0
    
12. #

复制代码

大佬 您的思路在这种样例上有点过不了 （但不一定有直接的公路相连，只要能间接通过公路可达即可）因为可以间接相通 所以本来输出应该是

1. 50
   
2. 50

复制代码

但是我们现在只能输出

1. no found!
   
2. 50

复制代码

这要怎么办呀

逃兵

欧德奈瑞 发表于 2020-12-13 11:42
大佬 您的思路在这种样例上有点过不了 （但不一定有直接的公路相连，只要能间接通过公路可达即可）因为 ...

是我不严谨了，我再想想

欧德奈瑞

逃兵 发表于 2020-12-14 08:15
是我不严谨了，我再想想

感谢大佬 麻烦您了

逃兵

欧德奈瑞 发表于 2020-12-14 10:00
感谢大佬 麻烦您了

1. def test(values,village_num):
   
2.     templst=[]
   
3.     try:
   
4.         templst.append(village_dic[values])
   
5.     except:
   
6.         pass
   
7.     for i in range(1,village_num+1):
   
8.             if i not in values:
   
9.                 try:
   
10.                     roads = village_dic[tempfun(values[0],i)]+village_dic[tempfun(i,values[1])]
    
11.                     templst.append(roads)
    
12.                 except:
    
13.                     pass      
    
14.     return templst
    
15. def tempfun(x,y):
    
16.     if x > y:
    
17.         return (y,x)
    
18.     else:
    
19.         return (x,y)
    
20. temp = 0
    
21. lst=[]
    
22. lst2=[]
    
23. while temp != '#':
    
24.     temp=input()
    
25.     lst +=[temp]
    
26. 
    
27. for i in range(len(lst)):
    
28.     if lst[i].count(' ') == 1:
    
29.         lst2.append(lst[i:i+int(lst[i][-1])+1])
    
30. lst2=lst2[:-1]
    
31. for i in lst2:
    
32.     village_num = int(i[0][0])
    
33.     village_dic={}
    
34.     newdic={}
    
35.     dickeys = [(j,i) for i in range(1,village_num+1) for j in range(1,i)]
    
36.     try:
    
37.         for j in i[1:]:
    
38.             lstj=j.split()
    
39.             x = int(lstj[0])
    
40.             y = int(lstj[1])
    
41.             z = int(lstj[2])
    
42.             village_dic[(x,y)]=z
    
43.         for values in dickeys:
    
44.             templst = test(values,village_num)
    
45.             newdic[values] = templst
    
46.         minlst=[]
    
47.         for i in newdic:
    
48.             minlst.append(min(newdic[i]))
    
49.         print(max(minlst))
    
50.     except:
    
51.         print('no found!')
    

复制代码

多给点例子我测测

欧德奈瑞

逃兵 发表于 2020-12-14 11:29
多给点例子我测测

大佬您看看 非常感谢
输入样例2:

1. 4 5
   
2. 1 2 10
   
3. 1 3 40
   
4. 1 4 10
   
5. 2 4 20
   
6. 3 4 50
   
7. 5 6
   
8. 1 2 20
   
9. 1 3 10
   
10. 1 4 20
    
11. 1 5 10
    
12. 2 5 30
    
13. 4 5 30
    
14. 6 6
    
15. 1 2 20
    
16. 1 4 30
    
17. 1 6 50
    
18. 2 3 10
    
19. 4 5 20
    
20. 5 6 10
    
21. 0 0
    
22. #

复制代码

输出样例2:

1. 60
   
2. 60
   
3. 90

复制代码

逃兵

欧德奈瑞 发表于 2020-12-14 19:05
大佬您看看 非常感谢
输入样例2:

例2
01
我计算出来的每一种公路长度
{(1, 2): [10, 30], (1, 3): [40, 60], (2, 3): [50, 70], (1, 4): [10, 30, 90], (2, 4): [20, 20], (3, 4): [50, 50]}
最短不应该是50吗
02
我计算出来的每一种公路长度
{(1, 2): [20, 40], (1, 3): [10], (2, 3): [30], (1, 4): [20, 40], (2, 4): [40, 60], (3, 4): [30], (1, 5): [10, 50, 50], (2, 5): [30, 30], (3, 5): [20], (4, 5): [30, 30]}
最短不应该是40吗
03
需要两次周转才能计算，这里没有计算

是不是我没有理解题目的意思

欧德奈瑞

逃兵 发表于 2020-12-14 21:26
例2
01
我计算出来的每一种公路长度

大佬 以下是唯一样例 您看看
输入样例

1. 3 3
   
2. 1 2 1
   
3. 1 3 2
   
4. 2 3 4
   
5. 4 6
   
6. 1 2 1
   
7. 1 3 4
   
8. 1 4 1
   
9. 2 3 3
   
10. 2 4 2
    
11. 3 4 5
    
12. 3 1
    
13. 1 2 1
    
14. 4 3
    
15. 1 2 4
    
16. 1 4 2
    
17. 2 4 1
    
18. 4 0
    
19. 6 9
    
20. 1 2 34
    
21. 1 3 46
    
22. 1 6 19
    
23. 2 5 12
    
24. 3 4 17
    
25. 3 6 25
    
26. 4 5 38
    
27. 4 6 25
    
28. 5 6 26
    
29. 0 0
    
30. #

复制代码

输出样例

1. 3
   
2. 5
   
3. no found!
   
4. no found!
   
5. no found!
   
6. 99

复制代码

大佬 应该是您的理解有一点偏差 “要求铺设的公路总长度为最小。请计算最小的公路总长度”  是说求能保证村村相通的各条公路的总长度之和最小的这个数值 比如上面最后一组样例输出99=19+25+17+26+12画个图大佬应该就可以看得出来啦

逃兵

1. class Graph(object):
   
2.   def __init__(self, maps):
   
3.     self.maps = maps
   
4.     self.nodenum = self.get_nodenum()
   
5.     self.edgenum = self.get_edgenum()
   
6.   
   
7.   def get_nodenum(self):
   
8.     return len(self.maps)
   
9.   
   
10.   def get_edgenum(self):
    
11.     count = 0
    
12.     for i in range(self.nodenum):
    
13.       for j in range(i):
    
14.         if self.maps[i][j] > 0 and self.maps[i][j] < 9999:
    
15.           count += 1
    
16.     return count
    
17.   
    
18.   def kruskal(self):
    
19.     res = []
    
20.     if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
    
21.       return res
    
22.     edge_list = []
    
23.     for i in range(self.nodenum):
    
24.       for j in range(i,self.nodenum):
    
25.         if self.maps[i][j] < 9999:
    
26.           edge_list.append([i, j, self.maps[i][j]])#按[begin, end, weight]形式加入
    
27.     edge_list.sort(key=lambda a:a[2])#已经排好序的边集合
    
28.      
    
29.     group = [[i] for i in range(self.nodenum)]
    
30.     for edge in edge_list:
    
31.       for i in range(len(group)):
    
32.         if edge[0] in group[i]:
    
33.           m = i
    
34.         if edge[1] in group[i]:
    
35.           n = i
    
36.       if m != n:
    
37.         res.append(edge)
    
38.         group[m] = group[m] + group[n]
    
39.         group[n] = []
    
40.     return res
    
41. def tempfun(x,y):
    
42.     if x > y:
    
43.         return (y,x)
    
44.     else:
    
45.         return (x,y)
    
46. lst=[]
    
47. lst2=[]
    
48. temp=0
    
49. while temp != '#':
    
50.     temp=input()
    
51.     lst +=[temp]
    
52. for i in range(len(lst)):
    
53.     if lst[i].count(' ') == 1:
    
54.         lst2.append(lst[i:i+int(lst[i][-1])+1])
    
55. lst2=lst2[:-1]
    
56. for i in lst2:
    
57.     village_num = int(i[0][0])
    
58.     village_dic={}
    
59.     newdic={}
    
60.     dickeys = [(j,i) for i in range(1,village_num+1) for j in range(1,i)]
    
61.     for j in i[1:]:
    
62.         lstj=j.split()
    
63.         x = int(lstj[0])
    
64.         y = int(lstj[1])
    
65.         z = int(lstj[2])
    
66.         village_dic[(x,y)]=z
    
67.     for keys in dickeys:
    
68.         if keys not in village_dic:
    
69.             village_dic[keys]=9999
    
70.     for num in range(1,village_num+1):
    
71.         village_dic[(num,num)] = 0
    
72.     maps = []
    
73.     templst = []
    
74.     for x in range(1,village_num+1):
    
75.         for y in range(1,village_num+1):
    
76.             templst.append(village_dic[tempfun(x,y)])
    
77.         maps.append(templst)
    
78.         templst=[]
    
79.     graph = Graph(maps)
    
80.     if len(graph.kruskal()) < village_num-1:
    
81.         print('no found!')
    
82.     else:
    
83.         roadsum = 0
    
84.         for i in graph.kruskal():
    
85.             roadsum+=i[-1]
    
86.         print(roadsum)
    

复制代码

查了很多很多资料，学了很多东西，受教了

逃兵

逃兵 发表于 2020-12-15 11:21
查了很多很多资料，学了很多东西，受教了

参考链接