圖論題，題目重新敘述為：

一棵樹從根出發遍歷完所有節點的最短總路徑之和

令 \(p(x)\) 表示節點 \(x\) 到根的路徑長，\(sum\) 表示所求總路徑之和，則：

\(sum_{min}=2 \times \sum_i ductLength_i - max\{p(x)\}\)

證明

最優解與深度優先遍歷有關，先證明如下問題：

若最終遍歷還要回到根節點，則最短路徑之和 \(sum2_{min}\) 就是深度優先遍歷的路徑之和 \(deepsum\)

利用歸納法可以證明深度優先遍歷路徑和?\(deepsum=2 \times \sum_i ductLength_i\)

若最終遍歷回到根節點，則任何一條邊必然至少被遍歷兩次，因此 \(sum2_{min} \geq 2 \times \sum_i ductLength_i\)，所以：

\(sum2_{min}=deepsum=2 \times \sum_i ductLength_i\)

將回到根節點的遍歷法分為兩步：

1. 遍歷到最后一個節點 \(x\)

2. 回到根節點

因此：

\(\ sum2=sum+p(x)\)

\(\begin{equation}\begin{split}sum_{min}&=sum2_{min}-max\{p(x)\} \\ &=2 \times \sum_i ductLength_i - max\{p(x)\}\end{split}\end{equation}\)

可以證明深度優先遍歷時使得 \(sum2\) 取最小值和 \(p(x)\) 取最大值并不沖突，綜上，命題得證

?

1 class Graph: 2 def __init__(self, n): 3 self.n = n # 節點個數 4 self.g = [[] for i in range(n)] # 鄰接表表示的圖模型 5 6 def count(self): 7 return self.n 8 9 10 # 新增一條邊 11 def append(self, i, j, l=None): 12 self.g[i].append((j, l)) 13 14 15 # 返回從x的后繼邊的集合 16 def nexts(self, x): 17 return self.g[x] 18 19 # DFS算法 20 class DeepFirstSearch: 21 def __init__(self, begin, g): 22 self.begin = begin # 開始節點 23 self.searchHandle = None # 搜到新節點時觸發 24 self.g = g # 搜索圖 25 26 def _onSearch(self, prev, nextNode, l): 27 if self.searchHandle != None: 28 self.searchHandle(prev, nextNode, l) 29 30 def do(self): 31 a = [self.begin] 32 marks = [False] * self.g.count() 33 marks[self.begin] = True 34 while len(a) > 0: 35 x = a.pop() 36 for yl in self.g.nexts(x): 37 y = yl[0] 38 l = yl[1] 39 if not marks[y]: 40 self._onSearch(x, y, l) 41 marks[y] = True 42 a.append(y) 43 44 45 class PowerOutage: 46 def search(self, x, y, l): 47 self.deeps[y] = self.deeps[x] + l 48 self.maxDeep = max(self.maxDeep, self.deeps[y]) 49 50 def estimateTimeOut(self, f, t, l): 51 maxNodeCount = 50 52 g = Graph(maxNodeCount) 53 for i in range(len(f)): 54 g.append(f[i], t[i], l[i]) 55 56 self.deeps = [0] * maxNodeCount 57 self.maxDeep = 0 58 dfs = DeepFirstSearch(0, g) 59 dfs.searchHandle = self.search 60 dfs.do() 61 62 result = 2 * sum(l) - self.maxDeep 63 return result 64 65 66 # test 67 o = PowerOutage() 68 69 # test case 70 assert(o.estimateTimeOut((0,), (1,), (10,)) == 10) 71 assert(o.estimateTimeOut((0,1,0), (1,2,3), (10,10,10)) == 40) 72 assert(o.estimateTimeOut((0,0,0,1,4), (1,3,4,2,5), (10,10,100,10,5)) == 165) 73 assert(o.estimateTimeOut((0,0,0,1,4,4,6,7,7,7,20), (1,3,4,2,5,6,7,20,9,10,31), (10,10,100,10,5,1,1,100,1,1,5)) == 281) 74 assert(o.estimateTimeOut((0,0,0,0,0), (1,2,3,4,5), (100,200,300,400,500)) == 2500) View Code

?

?

?

轉載于:https://www.cnblogs.com/valaxy/p/3440806.html

總結

以上是生活随笔為你收集整理的SRM144 DIV2 1100的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。