1

N頂点に 1 から N の番号が付けられた無向木があるとします。各エッジ ツリーにはある程度の容量があります。考えられるすべての頂点のペア間の最大フローの合計を見つけます。任意の 2 つの頂点間を移動する方法は 1 つしかありません。
考えられるすべての頂点のペア間の最大フローの合計を見つけます。

例: 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. Sortedge_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 on Tree


アップデート

制約-

  1. テストケース数 - 10
  2. 1 <= N <= 10 5 (各テスト ケースの頂点の数)
  3. 各エッジの容量は負ではなく、10 6を超えません。
  4. すべてのテスト ケースの頂点の総数は 5*10 5未満になります。
4

4 に答える 4

1

サブツリーのサイズをカウントするために毎回 2 つの新しい DFS を実行する代わりに、各エッジ uv について、エッジ uv が削除されたときに形成される u をルートとするサブツリー内のノードの数を計算する、よりスマートな DFS を 1 回だけ実行します。(uv と vu の両方について、この値を計算する必要があることに注意してください。)

これらのノード数を線形時間で計算する方法については、この素晴らしい回答を参照してください。

于 2016-04-19T13:36:59.773 に答える