如题。这个题洛谷上的数据是不符合:
对每个 i 和 j,1≤ci,pj≤106,如果 i=i′,则 ci=ci′;
也即最开始的每条边的边权不同这个条件的。
我起初猜想,可能是洛谷早期用的是民间数据,于是从死去的 BZOJ 扒了一份数据,发现 BZOJ 的数据也不满足这个要求。
此外,我还获取到过一份 APIO 数据,且修改日期为 2013 年 5 月 10 日,将其进行测试同样的测试,发现依然不满足该约束。
那一年的 APIO 官网 http://apio.comp.nus.edu.sg 和 http://apio.olympiad.org 全都无法访问了,因此我也没法进一步确认。
希望有人能够提供一份确保无误的官方数据,或者证明官方数据就是错完了,好让我们可以没有心理负担地改数据。