给定一棵无向树,其N
顶点编号从 1 到 N。每棵边树都有一定的容量。求所有可能的顶点对之间的最大流量之和。在任何两个顶点之间只存在一种方式。
求所有可能的顶点对之间的最大流量之和。
例如:在具有 3 条边的给定树中,
1 2 5
2 3 6
节点 1 和节点 2 之间的边容量为 5,节点 2 和节点 3 之间的边容量为 6。
Output - 32
(1,2) = (2,1) = 5
(1,3) = (3,1) = 5
(2,3) = (3,2) = 6
因此输出为(5+5+6)*2 = 32
我的方法-
Sort
基于 edge_capacity 的边While
edge_list
isnot empty
: 以最小容量移除边- 计算该边上
left
的节点数。right
对节点数进行 DFS - 将 (
left_count
*right_count
*edge_capacity
) 添加到答案中。
- 计算该边上
返回
answer*2
。
时间复杂度为 O(n 2 )。该解决方案提供 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
更新
约束——
- 测试用例数量 - 10
- 1 <= N <= 10 5 (每个测试用例中的顶点数)
- 每个边缘的容量将是非负的并且不超过 10 6。
- 所有测试用例中的顶点总数将小于 5*10 5。