蒟蒻关于仙人掌树的两个问题,各位神犇麻烦出手相救~~

P4244 [SHOI2008] 仙人掌图 II

@[xiaogongzhu](/user/68611) 1.您的 list 数组就是题解中的栈,在第 31 行你的代码中已有「list[1]=1;」,已把环中第 1 个点存入栈中,无需重复再存。 您觉得重复不会影响,实际上,此时栈中存了两次有关第 1 个点的信息,这是不合法的,可能会在第 35 行 ans 取 max 时影响 ans 的值使答案偏大。 若要从 i=1 开始,要删去第 31 行「list[1]=1;」,并把同行中「head=tail=1」 改成「head=1,tail=0」,再在第 35 行前添加判断语句「if(head<=tail)」来特殊处理栈为空的情况即可。 2.这是 Tarjan 的板子,间接反映了您对 Tarjan 算法理解的不够透彻,建议您重新学习并理解 Tarjan 算法的流程,真正掌握它并能灵活运用。 「如果y不是x的爸爸且被访问过」,dfn[x] 确实大于 dfn[y],但是如果有两个(或多个) y 满足条件呢?这时按照您「去掉mymin,直接else low[x]=dfn[y]」的算法您的 low[x] 的值就等于最后一个更新的 dfn[y],因为后者会覆盖前者,这与 low 数组的定义不符。 我对这道题刚开始其实也有挺多疑惑,但花了大量时间思考,现在也明白了,希望这些内容还能帮到你及之后做这题的人!
by 18Michael @ 2021-02-24 21:59:48


|