algorithm - 最小生成树中所有节点之间每条可能路径的距离

Question

我想得到所有节点到所有节点的距离。关于这个有几个问题，但没有一个能解决我的问题。我的方法是我正在实现递归 DFS 并在回溯时存储每条路径的结果，但问题是我的运行时间很长，并且我经过了 N 次路径(N 是边数)。

正如您在我的代码中看到的，我正在为每个可能的节点作为根运行 dfs。我不知道如何在 DFS 搜索的一次迭代中重用路径来知道答案。

我认为它可以在 O(n) 中完成，因为它是最小生成树，并且一对节点之间只有一条路径。

我的代码:

vector<int> visited(50001);
map< pair<ll,ll> , ll> mymap;
map<ll, vector<ll> > graph;

void calc(ll start,ll node)
{
    visited[node]=1;
    vector<ll>::iterator it;
    for (it = graph[node].begin(); it != graph[node].end(); ++it)
    {
        if (!visited[*it])
        {
            ans+=mymap[make_pair(node,*it)];
            mymap[make_pair(start,*it)]=ans;
            calc(start, *it);
            ans-=mymap[make_pair(node,*it)];
        }
    }
}

主要内容:

for(i=1;i<=n;i++)
    {
        fill(visited.begin(),visited.end(),0);
        ans=0;
        calc(i,i);
    }

Answer 1

我可以想到使用分而治之的复杂度 O(n * logn) 的解决方案。让我分享一下。

让我们选择一条距离d 的边e 连接节点a 和b。让我们削减它。现在我们有两棵根为 a 和 b 的树。让我们假设，

• 树中的节点数 a = na
• 树a中每个节点之间的距离之和= ca
• 树a中每个节点到根的距离之和= ra
• 树中的节点数 b = nb
• 树b中每个节点之间的距离之和= cb
• 树b中每个节点到根的距离之和= r

所以原始树中每个节点之间的距离为: ca + cb + (nb * ra + na * d * nb + na * rb))

现在，我们可以使用相同的方法计算树a 或b 中每个节点的距离总和。需要注意的一件事是，我们必须选择这样的边 e 使得组件数量之间的差异不大。你总能在树中找到一条边，如果你切断这条边，得到的两棵树的节点数之差不会超过 1。