给定一棵无向树,其中 N
个顶点编号从 1 到 N。每棵边树都有一定的容量。找到所有可能的顶点对之间的最大流量之和。任意两个顶点之间只存在一种方式。
找到所有可能的顶点对之间的最大流量之和。
例如:在给定的有 3 条边的树中
1 2 5
2 3 6
节点 1 和节点 2 之间的边容量为 5,节点 2 和节点 3 之间的边容量为 6。
输出 - 32
(1,2) = (2,1) = 5
(1,3) = (3,1) = 5
(2,3) = (3,2) = 6
因此输出为 (5+5+6)*2 = 32
我的方法-
排序
基于edge_capacity的边当
edge_list
不为空
时:删除容量最小的边- 计算这条边的
左边
和右边
上的节点数。为节点计数做 DFS - 将 (
left_count
*right_count
*edge_capacity
) 添加到答案中。
- 计算这条边的
返回
答案*2
。
时间复杂度为 O(n2)。此解决方案提供 TLE。
如何进一步降低时间复杂度?
我的代码-
def dfs(node):
count = 1
visited = set()
stack = [node]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(set(nodes[vertex]) - visited)
return len(visited)
for _ in range(int(raw_input())): # Iterate for multiple test cases
MOD = 1000000007
edges = []
n = int(raw_input()) # number of vertices
nodes = [set() for _ in range(n)]
for __ in range(n-1): # read input for number of edges
edges.append(map(int, raw_input().split()))
nodes[edges[-1][0]-1].add(edges[-1][1]-1)
nodes[edges[-1][1]-1].add(edges[-1][0]-1)
edges[-1][0]-=1; edges[-1][1]-=1;
edges.sort(key=lambda x: x[2])
answer = 0
for i in range(len(edges)):
weight = edges[i][2]
x, y = edges[i][0], edges[i][1]
nodes[x].remove(y)
nodes[y].remove(x)
left_count = dfs(x)
right_count = dfs(y)
answer += ((left_count*right_count*weight)%MOD)
print (answer*2)%MOD
链接到原始问题-
Spoj-Flow on Tree
更新
约束-
- 测试用例数量 - 10
- 1 <= N <= 105(每个测试用例中的顶点数)
- 每条边的容量为非负且不超过 106。
- 所有测试用例的顶点总数将小于 5*105。
最佳答案
与其每次都运行两个新的 DFS 来计算子树的大小,不如运行一次更智能的 DFS,它为每条边 uv 计算删除边 uv 时形成的以 u 为根的子树中的节点数。 (请注意,您需要为 uv 和 vu 计算此值。)
有关以线性时间计算这些节点数的方法,请参阅 this nice answer .
关于algorithm - 树的每对顶点之间的最大流量之和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36711443/