求助 Python 最小生成树,Python交流,编程语言专区,鱼C论坛

欧德奈瑞 发表于 2020-12-11 21:54:48

求助 Python 最小生成树

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

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

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

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

输入样例:
在这里给出两组输入。例如：
3 3
1 2 10
1 3 20
2 3 40
4 6
1 2 10
1 3 40
1 4 10
2 3 30
2 4 20
3 4 50
0 0
#
输出样例:
在这里给出相应的输出。例如：
30
50

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

def tempfun(x,y):
if x > y:
   return (y,x)
else:
   return (x,y)
temp = 0
lst=[]
lst2=[]
while temp != '#':
temp=input()
lst +=

for i in range(len(lst)):
if lst.count(' ') == 1:
   lst2.append(lst[-1])+1])
lst2=lst2[:-1]
for i in lst2:
try:
   dic={}
   for j in i:
         lstj=j.split()
         x = int(lstj)
         y = int(lstj)
         z = int(lstj)
         dic[(x,y)]=z
   long=[]
   for cell in dic:
         temp=[]
         for num in range(1,max(dic.keys())+1):
            if num != cell and num != cell:
               temp.append(dic,num)]+dic,num)])
         temp.append(dic)
         m = min(temp)
         long.append(m)

   print(max(long))
except:
   print('no found!')

欧德奈瑞 发表于 2020-12-13 11:42:20

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

3 2
1 2 10
2 3 40
4 6
1 2 10
1 3 40
1 4 10
2 3 30
2 4 20
3 4 50
0 0
#
大佬您的思路在这种样例上有点过不了（但不一定有直接的公路相连，只要能间接通过公路可达即可）因为可以间接相通所以本来输出应该是
50
50
但是我们现在只能输出
no found!
50
这要怎么办呀{:10_266:}

逃兵发表于 2020-12-14 08:15:00

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

是我不严谨了，我再想想{:10_266:}

欧德奈瑞 发表于 2020-12-14 10:00:57

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

感谢大佬麻烦您了

逃兵发表于 2020-12-14 11:29:53

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

def test(values,village_num):
templst=[]
try:
   templst.append(village_dic)
except:
   pass
for i in range(1,village_num+1):
         if i not in values:
            try:
               roads = village_dic,i)]+village_dic)]
               templst.append(roads)
            except:
               pass
return templst
def tempfun(x,y):
if x > y:
   return (y,x)
else:
   return (x,y)
temp = 0
lst=[]
lst2=[]
while temp != '#':
temp=input()
lst +=

for i in range(len(lst)):
if lst.count(' ') == 1:
   lst2.append(lst[-1])+1])
lst2=lst2[:-1]
for i in lst2:
village_num = int(i)
village_dic={}
newdic={}
dickeys = [(j,i) for i in range(1,village_num+1) for j in range(1,i)]
try:
   for j in i:
         lstj=j.split()
         x = int(lstj)
         y = int(lstj)
         z = int(lstj)
         village_dic[(x,y)]=z
   for values in dickeys:
         templst = test(values,village_num)
         newdic = templst
   minlst=[]
   for i in newdic:
         minlst.append(min(newdic))
   print(max(minlst))
except:
   print('no found!')

多给点例子我测测

欧德奈瑞 发表于 2020-12-14 19:05:33

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

大佬您看看非常感谢
输入样例2:
4 5
1 2 10
1 3 40
1 4 10
2 4 20
3 4 50
5 6
1 2 20
1 3 10
1 4 20
1 5 10
2 5 30
4 5 30
6 6
1 2 20
1 4 30
1 6 50
2 3 10
4 5 20
5 6 10
0 0
#
输出样例2:
60
60
90

逃兵发表于 2020-12-14 21:26:40

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

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

是不是我没有理解题目的意思{:10_266:}

欧德奈瑞 发表于 2020-12-15 00:30:11

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

大佬以下是唯一样例您看看
输入样例
3 3
1 2 1
1 3 2
2 3 4
4 6
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
3 1
1 2 1
4 3
1 2 4
1 4 2
2 4 1
4 0
6 9
1 2 34
1 3 46
1 6 19
2 5 12
3 4 17
3 6 25
4 5 38
4 6 25
5 6 26
0 0
#
输出样例
3
5
no found!
no found!
no found!
99
大佬应该是您的理解有一点偏差 “要求铺设的公路总长度为最小。请计算最小的公路总长度”是说求能保证村村相通的各条公路的总长度之和最小的这个数值比如上面最后一组样例输出99=19+25+17+26+12画个图大佬应该就可以看得出来啦{:10_254:}

逃兵发表于 2020-12-15 11:21:55

class Graph(object):
def __init__(self, maps):
self.maps = maps
self.nodenum = self.get_nodenum()
self.edgenum = self.get_edgenum()

def get_nodenum(self):
return len(self.maps)

def get_edgenum(self):
count = 0
for i in range(self.nodenum):
   for j in range(i):
   if self.maps > 0 and self.maps < 9999:
      count += 1
return count

def kruskal(self):
res = []
if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
   return res
edge_list = []
for i in range(self.nodenum):
   for j in range(i,self.nodenum):
   if self.maps < 9999:
      edge_list.append(])#按形式加入
edge_list.sort(key=lambda a:a)#已经排好序的边集合

group = [ for i in range(self.nodenum)]
for edge in edge_list:
   for i in range(len(group)):
   if edge in group:
      m = i
   if edge in group:
      n = i
   if m != n:
   res.append(edge)
   group = group + group
   group = []
return res
def tempfun(x,y):
if x > y:
   return (y,x)
else:
   return (x,y)
lst=[]
lst2=[]
temp=0
while temp != '#':
temp=input()
lst +=
for i in range(len(lst)):
if lst.count(' ') == 1:
   lst2.append(lst[-1])+1])
lst2=lst2[:-1]
for i in lst2:
village_num = int(i)
village_dic={}
newdic={}
dickeys = [(j,i) for i in range(1,village_num+1) for j in range(1,i)]
for j in i:
   lstj=j.split()
   x = int(lstj)
   y = int(lstj)
   z = int(lstj)
   village_dic[(x,y)]=z
for keys in dickeys:
   if keys not in village_dic:
         village_dic=9999
for num in range(1,village_num+1):
   village_dic[(num,num)] = 0
maps = []
templst = []
for x in range(1,village_num+1):
   for y in range(1,village_num+1):
         templst.append(village_dic)
   maps.append(templst)
   templst=[]
graph = Graph(maps)
if len(graph.kruskal()) < village_num-1:
   print('no found!')
else:
   roadsum = 0
   for i in graph.kruskal():
         roadsum+=i[-1]
   print(roadsum)

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

逃兵发表于 2020-12-15 11:36:18

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

参考链接

页: [1]

鱼C论坛's Archiver

求助 Python 最小生成树