题解中 StudyingFather 的代码有误,并被 hack。
参考数据(并请求添加):
3 2
2 1 -1
3 2 -1
SF 的代码输出为 NO
,实际上存在一组解为
0 -1 -2
代码错误的地方为:
if(tot[v]==n) return false;
显然,在 SF 的做法中,新建了一个超级源点,实际上判负环应该为 tot[v]==n+1
。具体可以看这个帖子。
虽然这个错误很细微也很低级,但可能会误导新手,并且个人觉得有必要在题解中提醒注意这些细节。(这个错误之前在 Johnson 模板里就出现过了)