Kruskal+倍增lca 15pts警钟长鸣
查看原帖
Kruskal+倍增lca 15pts警钟长鸣
734630
justin_jiajia蒟蒻楼主2024/10/7 17:42

省流:注意 if (u == v) return res;

以下是我的代码:

int getmin(int u, int v) {
  if (not intree[u] or not intree[v]) return -1;
  if (deep[u] > deep[v]) swap(u, v);
  int res = inf;
  // now:deep[v]>=deep[u]
  // pull v up
  for (int i = lgmxn - 1; i >= 0; --i)
    if (deep[fa[v][i]] >= deep[u]) {
      res = min(res, minw[v][i]);
      v = fa[v][i];
    }
  //这里缺少!
  for (int i = lgmxn - 1; i >= 0; --i)
    if (fa[u][i] != fa[v][i]) {
      res = min({res, minw[u][i], minw[v][i]});
      u = fa[u][i], v = fa[v][i];
    }
  res = min({res, minw[u][0], minw[v][0]});
  return res;
}

开始死活找不到错误,跟#1题解对比发现少了 if (u == v) return res;

考虑两个节点为祖先-后代关系。当第一次将两个节点抬升到同深度后虽然不会进行“同时倍增跳”的环节但是 res = min({res, minw[u][0], minw[v][0]}); 依然被执行。连接这个节点与父亲的边权被错误计算。

2024/10/7 17:42
加载中...