关于代码顺序

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

jingkongwanglimiaoa @ 2020-08-20 13:44:34

这是一道欧拉板子题尽管是模板但本蒟蒻还是一如既往的迷惑呢

经过长时间地坚持看题解,我终于A了这道题

但本蒟蒻还是有个问题没搞明白,先贴两段代码

1.正确AC代码
void dfs(int x)//深搜 
{ 
    for (int i = 0;i <= maxn;i++)//maxn指最大数值的点
    if (e[x][i]) 
    {
        e[x][i]--;//删边 ,e数组表示两个点有几条边
        e[i][x]--;
        dfs(i);
    }
    q[++hd] = x;    //hd为队尾,x入队
}
2.不正常WA两个点代码
void dfs(int x)//深搜 
{ 
    q[++hd] = x;    //hd为队尾,x入队
    for (int i = 0;i <= maxn;i++)//maxn指最大数值的点
    if (e[x][i]) 
    {
        e[x][i]--;//删边 
        e[i][x]--;
        dfs(i);
    }
}

两个代码几乎一模一样,就改了一行代码的顺序,它就wa了两个点,输出那里我一个倒序一个正序是莫得问题的,真是个玄学错误

奇妙蒟蒻遇玄学错误


by mot1ve @ 2020-08-20 14:03:37

这个图 如果从1出发的话,终点一定是3,你那样存,从1出发显然会把3的位置存错。而递归求的话就会把3放到栈底部。这样保证3是终点。


by mot1ve @ 2020-08-20 14:04:24

我画的这个图其实是欧拉路径 不是欧拉回路 但其实原理一样的 你错误的点在这个图也适用


by jingkongwanglimiaoa @ 2020-08-20 19:48:45

啊我懂了,如果我想要把入队操作放前面的话就要加上回溯,然而加了回溯后会TLE(duliu!!


by jingkongwanglimiaoa @ 2020-08-20 19:49:39

@kuoluo03 谢谢神犇


上一页 |