玄学的错误

P1983 [NOIP2013 普及组] 车站分级

_Iva @ 2022-10-24 16:29:50

while(!q.empty())
    {
        u = q.front(), q.pop();
        as = max(as, dp[u]);
        for(int e = hed[u]; e; e = nxt[e])
        {
            v = to[e];
            dp[v] = max(dp[v], dp[u] + (v <= n)); //
            if(!--d[v]) q.push(v);
        }
    }
WA$ 成 $20pt

改成

while(!q.empty())
    {
        u = q.front(), q.pop();
        if(u > n) --dp[u]; //
        as = max(as, dp[u]);
        for(int e = hed[u]; e; e = nxt[e])
        {
            v = to[e];
            dp[v] = max(dp[v], dp[u] + 1); //
            if(!--d[v]) q.push(v);
        }
    }

A


by _Iva @ 2022-10-24 16:33:22

我是用的建虚点做法,>n是虚点


by Sprague_Garundy @ 2022-10-24 16:37:48

@_Iva 一个是 u 一个是 v 当然不一样啊?


by _Iva @ 2022-10-24 16:55:04

破案了,因为虚点有可能是起点,而我初始设的 dp_u=1 ,若第一种写法就会出错。把第一种情况初始化改为 dp_u = (u<=n) 也过了


|