减去阈值的位置为什么会影响答案?
查看原帖
减去阈值的位置为什么会影响答案?
56749
default111楼主2020/11/5 23:45

拓扑排序,详见图,二维数组存图,每遍历一个边下一个节点的入度-1直到入度为0加入队列。 问题在于, 我之前写的是在每次从队列里取出一个节点后将阈值减去(注释掉的那行),再遍历边; 题解里dl是在入队时将阈值减去。 将减去阈值的位置改成入队时就AC了,取出时减去就WA #3 #5 求问这是为什么

while(!topo.empty())
    {
        int cur=topo.front();
        topo.pop();
        //c[cur]-=u[cur];
        for(int i=1;i<=n;i++)
        {
            if(mp[cur][i]!=INF)
            {
                in[i]--;
                if(c[cur]>0) c[i]=c[i]+c[cur]*mp[cur][i];
                if(in[i]==0) {
                    topo.push(i);
                    c[i]-=u[i];
                }
            }
        }
    }
2020/11/5 23:45
加载中...