关于第11个点WA以及SPFA判负环的疑问
查看原帖
关于第11个点WA以及SPFA判负环的疑问
416483
Niouville楼主2021/7/25 01:14

为什么这样过不了Point11?(会错判成有负环)

if (h[to] > h[node] + edge[i].value)
{
	h[to] = h[node] + edge[i].value;
	qcnt[to]++;
	if (qcnt[to] > n)
		return false;
	if (!inqueue[to])
		q.push(to), inqueue[to] = true;
}

这样就可以:

if (h[to] > h[node] + edge[i].value)
{
	h[to] = h[node] + edge[i].value;
	if (!inqueue[to])
	{
		q.push(to), inqueue[to] = true;
		qcnt[to]++;
		if (qcnt[to] > n)
			return false;
	}
}

也就是说每更新一次不就应该松弛次数+1吗?而松弛不一定要入列(可能已经在队列里面)那为什么松弛次数的更新和判断不能放在外面?

2021/7/25 01:14
加载中...