我有一个问题要解决涉及控制彼此利益的公司.如果A拥有超过50%的B,或者A拥有一系列其他公司,并且拥有超过50%的B,则公司控制另一家公司.
我正在用一个顶点和边的图表来接近这个,它代表了与所有公司的所有关系.
我认为我需要实现的是广度优先搜索(或者可能是最长路径而不是最短路径的Dijkstra算法设备)沿着企业之间的路径,只要从A到B的路径总和加权大于50% .我不知道如何实现这一点,因为我只能使用标准的Python 3.x库来解决这个问题.任何帮助将不胜感激!
样本输入
CompanyA CompanyB 30 CompanyB CompanyC 52 CompanyC CompanyD 51 CompanyD CompanyE 70 CompanyE CompanyD 20 CompanyD CompanyC 20
样本输出
CompanyA has a controlling interest in no other companies. CompanyB has a controlling interest in CompanyC, CompanyD, and CompanyE. CompanyC has a controlling interest in CompanyD, and CompanyE. CompanyD has a controlling interest in CompanyE. CompanyE has a controlling interest in no other companies.
我的代码到目前为止:
import sys class Vertex: def __init__(self, key): self.id = key self.connectedTo = {} def addNeighbour(self, nbr, weight = 0): self.connectedTo[nbr] = weight def __str__(self): return str(self.id) + 'connectedTo: ' + str([x.id for x in self.connectedTo]) def getConnections(self): return self.connectedTo.keys() def getId(self): return self.id def getWeight(self, nbr): return self.connectedTo[nbr] class Graph: def __init__(self): self.vertList = {} self.numVerticies = 0 def addVertex(self, key): self.numVerticies = self.numVerticies + 1 newVertex = Vertex(key) self.vertList[key] = newVertex return newVertex def getVertex(self,n): if n in self.vertList: return self.vertList[n] else: return None def __contains__(self, n): return n in self.vertList def addEdge(self, f, t, cost = 0): if f not in self.vertList: nv = self.addVertex(f) if t not in self.vertList: nv = self.addVertex(t) self.vertList[f].addNeighbour(self.vertList[t], cost) def getVertices(self): return self.vertList.keys() def __iter__(self): return iter(self.vertList.values()) #all code above this line deals with the ADTs for Vertex and Graph objects #all code below this line deals with taking input, parsing and output def main(): f = sys.argv[1] #TODO deal with standard input later temp = graphFunction(f) def graphFunction(filename): openFile = open(filename, 'r') coList = [] g = Graph() for line in openFile: lineSplit = line.split() g.addEdge(lineSplit[0], lineSplit[1], lineSplit[2]) coList.append(lineSplit[0]) coList.append(lineSplit[1]) coSet = set(coList) coList = list(coSet) #converting this from a list to a set to a list removes all duplicate values within the original list openFile.close() #this is where there should be a Breadth First Search. Notthing yet, code below is an earlier attempt that kinda sorta works. newConnList = [] #this is a list of all the new connections we're going to have to make later for v in g: #for all verticies in the graph for w in v.getConnections(): #for all connections for each vertex #print("%s, %s, with weight %s" % (v.getId(), w.getId(), v.getWeight(w))) #print(v.getId(), w.getId(), v.getWeight(w)) firstCo = v.getId() secondCo = w.getId() edgeWeight = v.getWeight(w) if int(edgeWeight) > 50: #then we have a controlling interest situation for x in w.getConnections(): firstCo2 = w.getId() secondCo2 = x.getId() edgeWeight2 = w.getWeight(x) #is the secondCo2 already in a relationship with firstCo? if x.getId() in v.getConnections(): #add the interest to the original interest tempWeight = int(v.getWeight(x)) print(tempWeight) tempWeight = tempWeight + int(w.getWeight(x)) newConnList.append((firstCo, secondCo2, tempWeight)) #and create a new edge print('loop pt 1') else: newConnList.append((firstCo, secondCo2, edgeWeight2)) for item in newConnList: firstCo = item[0] secondCo = item[1] edgeWeight = item[2] g.addEdge(firstCo, secondCo, edgeWeight) #print(item) for v in g: for w in v.getConnections(): print(v.getId(), w.getId(), v.getWeight(w)) main()
Games Braini.. 5
我认为深度优先搜索将是一种更好的方法,因为你需要拥有谁.
所以,我所做的是创建一个名为的文本文件com.txt
,并在其中:
A B 30 B C 52 C D 51 D E 70 E D 20 D C 20
这是脚本:
来自集合的import defaultdict,deque
with open('com.txt', 'r') as companies: # Making a graph using defaultdict connections = defaultdict(list) for line in companies: c1, c2, p = line.split() connections[c1].append((c2, int(p))) for item in connections: q = deque([item]) used = set() memory = [] while q: c = q.pop() if c in connections and c not in used: memory.append(c) to_add = [key for key, cost in connections[c] if cost > 50] if to_add: q.extend(to_add) used.add(c) else: break if len(memory) < 2: print(memory[0], "does not own any other company") else: owner = memory[0] comps = memory[1:] print(owner, "owns", end=' ') print(" and ".join(comps)) del used
当我第一次建立连接列表时,我过滤掉了没有公司 50%所有权的变量.这个脚本产生:
{'A': [('B', 30)], 'C': [('D', 51)], 'B': [('C', 52)], 'E': [('D', 20)], 'D': [('E', 70), ('C', 20)]} A does not own any other company C owns D and E B owns C and D and E E does not own any other company D owns E
正如所料.
我认为深度优先搜索将是一种更好的方法,因为你需要拥有谁.
所以,我所做的是创建一个名为的文本文件com.txt
,并在其中:
A B 30 B C 52 C D 51 D E 70 E D 20 D C 20
这是脚本:
来自集合的import defaultdict,deque
with open('com.txt', 'r') as companies: # Making a graph using defaultdict connections = defaultdict(list) for line in companies: c1, c2, p = line.split() connections[c1].append((c2, int(p))) for item in connections: q = deque([item]) used = set() memory = [] while q: c = q.pop() if c in connections and c not in used: memory.append(c) to_add = [key for key, cost in connections[c] if cost > 50] if to_add: q.extend(to_add) used.add(c) else: break if len(memory) < 2: print(memory[0], "does not own any other company") else: owner = memory[0] comps = memory[1:] print(owner, "owns", end=' ') print(" and ".join(comps)) del used
当我第一次建立连接列表时,我过滤掉了没有公司 50%所有权的变量.这个脚本产生:
{'A': [('B', 30)], 'C': [('D', 51)], 'B': [('C', 52)], 'E': [('D', 20)], 'D': [('E', 70), ('C', 20)]} A does not own any other company C owns D and E B owns C and D and E E does not own any other company D owns E
正如所料.