拓扑排序,详见图,二维数组存图,每遍历一个边下一个节点的入度-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];
}
}
}
}