2

我的问题非常直截了当。

给出了一个加权树。我们必须找到两个给定节点之间的距离。

因为每次 bfs 超时时查询的数量都非常高（大约 75000），所以我尝试了不同的方法来做到这一点。

我的算法是这样的：

  • 我从顶点0运行dfs并计算从root（0）到所有顶点的距离，就像这样

        depth[v]=depth[u]+w,where u is parent of v and w is weight b/w (u,v)

  • 一旦我使用 dfs 和每个节点的第 2^j 个父节点计算了所有节点的深度（假设我知道该怎么做）。我计算了每个查询的 (u,v) 的 LCA 。

  • 然后我像这样计算距离

        distance between (u,v)=depth[u]+depth[v]-2*depth[lca(u,v)]

但我没有得到预期的正确判决。我的算法是正确的还是我错过了一些重要的东西。需要指导:)

Ps 万一有人想看我的实现-链接http://paste.ubuntu.com/13129038/

4

1 回答 1

1

您的方法听起来很合理，但是查看链接代码，我建议您尝试一个小示例（例如，树中有 3 个节点）并仔细检查父数组的内容。

据我所见，更改父数组内容的唯一行是：

memset(parent,-1,sizeof parent);

和

parent[i][j]=parent[i-1][parent[i-1][j]]

所以我相信父母的内容总是等于-1。

也许您需要一个基本案例设置 parent[0][j] 等于 j 的父级？

此外，从代码中还不清楚您是使用深度来表示边数的计数，还是所有边权重的总和。要使距离计算起作用，您需要权重总和，但要使 LCA 算法起作用，您可能会发现需要使用边数。

于 2015-11-06T20:32:20.210 回答