奇怪的错法求hack
查看原帖
奇怪的错法求hack
443664
Missa楼主2022/4/7 12:13

nn 个点,每个点有且仅有一条出边,应该就是一个内向基环树森林。

不在环上的可以直接走到环上,所以答案相当于:给定一个基环树森林,点有点权,求 点权和-每个环上选一个点的点权 的最大值。

考场时,我是先一遍拓扑找环,然后顺着环dfs下去的,只有63pts。这里顺着环dfs的实现方法是:(把单向边连成双向边的情况下)找到所有与 uu 相连的点,如果 vv 在环上且 vv 不是来时的那个点,就顺着 vv 走下去。后来,我直接把 vv 改成了 aua_u,就过了。

现在蒟蒻非常不解,为什么按这个方法找到的 vv 不一定是 aua_u 呢?

2022/4/7 12:13
加载中...