1

给定一棵无向树，其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

我的方法-

  1. Sort基于 edge_capacity 的边

  2. While edge_listis not empty: 以最小容量移除边

    • 计算该边上left的节点数。right对节点数进行 DFS
    • 将 ( left_count* right_count* edge_capacity) 添加到答案中。

  3. 返回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


更新

约束——

  1. 测试用例数量 - 10
  2. 1 <= N <= 10 5 （每个测试用例中的顶点数）
  3. 每个边缘的容量将是非负的并且不超过 10 6。
  4. 所有测试用例中的顶点总数将小于 5*10 5。
4

4 回答 4

1

与其每次运行两个新的 DFS 来计算子树的大小，不如只运行一次更智能的 DFS，它会为每个边 uv 计算在删除边 uv 时形成的以 u 为根的子树中的节点数。（请注意，您需要为 uv 和 vu 计算此值。）

有关以线性时间计算这些节点计数的方法，请参阅这个不错的答案。

于 2016-04-19T13:36:59.773 回答
0

这个想法是最大化具有最高度数的顶点的N值。

    public static int highestSum(int N, int[] A, int[] B) {

    // Initialize a DP array to save the Degree of Each Vertex of Graph
    int[] dp = new int[N + 1];
    int sum = 0;
    // Iterate over A and B and increase the index value in DP array
    for (int i = 0; i < A.length; i++) {
        dp[A[i]]++;
        dp[B[i]]++;
    }
    // Sort the array so that we can assign max value of N to Vertex with maximum
    // //degree
    Arrays.sort(dp);
    for (int j = dp.length - 1; j > 0; j--) {
        sum += dp[j] * j;
    }
    return sum;
}
于 2022-01-11T17:36:56.513 回答
0

这是另一种基于Kruskal 算法和Union Find的有趣方法：

algorithm Kruskal(G) is
    res := 0
    size := {v:1 for v in G.V}
    for each (u,v) in G.E ordered by weight(u,v) decreasing do
        u' := FIND-SET(u)
        v' := FIND-SET(v)
        res += weight(u,v) * size[u'] * size[v']
        w' := UNION(u', v')
        size[w'] = size[u'] + size[v']
    return res

通过首先组合大边，我们总是知道我们正在研究的新边是子树中最小的。

如果您的边缘已经按重量排序，则基本上是线性时间。

于 2021-09-12T04:27:45.643 回答
0

想法是通过按降序对边进行排序并找到每个联合的路径数来使用 DSU。

更有趣和更难的版本出现在 Facebook Hackercup 2021 第 1 轮中，您必须在其中做同样的事情，但每个边缘都断开连接。问题链接：https ://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/C

于 2021-09-13T19:56:21.477 回答