80pts求调

P2597 [ZJOI2012] 灾难

要建新图吧(蒟蒻发问)
by LEE114514 @ 2023-08-01 15:06:53


把所有无入度的点连到超级源上,遍历子节点然后把子节点的父节点改为遍历前的父节点和当前节点的LCA
by LEE114514 @ 2023-08-01 15:09:04


@[LEE114514](/user/750579) 没听懂啊大佬qwq,能不能细说
by czy0323 @ 2023-08-01 19:29:11


@[czy0323](/user/538427) 本蒟蒻把所有原图中入度为0的点找出来,建一张新图。在新图中连到一个新点上。从新点开始bfs,如果假设目前到了节点 u,它的一个子节点是 v,如果 v 在新图中没有父亲那就在新图中 u,v 连一条边,否则把 v 的父亲更新为它的父亲和 u 在新图中的 lca
by LEE114514 @ 2023-08-02 06:25:59


@[LEE114514](/user/750579) 大佬,这份代码已经调出来了,只是因为没把0的儿子dep设为1导致的qwq
by czy0323 @ 2023-08-02 08:31:54


|