SRM144 DIV2 1100

图论题，题目重新叙述为：

一棵树从根出发遍历完所有节点的最短总路径之和

令 (p(x)) 表示节点 (x) 到根的路径长，(sum) 表示所求总路径之和，则：

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

证明

最优解与深度优先遍历有关，先证明如下问题：

若最终遍历还要回到根节点，则最短路径之和 (sum2_{min}) 就是深度优先遍历的路径之和 (deepsum)

利用归纳法可以证明深度优先遍历路径和 (deepsum=2 imes sum_i ductLength_i)

若最终遍历回到根节点，则任何一条边必然至少被遍历两次，因此 (sum2_{min} geq 2 imes sum_i ductLength_i)，所以：

(sum2_{min}=deepsum=2 imes sum_i ductLength_i)

将回到根节点的遍历法分为两步：

1. 遍历到最后一个节点 (x)

2. 回到根节点

因此：

( sum2=sum+p(x))

(egin{equation}egin{split}sum_{min}&=sum2_{min}-max{p(x)} \ &=2 imes 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