只是提出一个设想,类似于抛砖引玉。
由于数据随机,虽然保证了图不存在负圈、SSP 等和 O(f) 有关的算法可以通过,但是也造成了数据很弱。
今天发现我的原始对偶板子有锅,并且因此在另一道网络流题上调了一个下午。
这个数据随机,就导致虽然我通过了此题,但不敢相信我的任何费用流板子是完全正确的。
所以,有没有可能可以删去此题数据随机的特殊性质,换为更具体的表述(如数据保证正常实现的……算法可以通过),并且添加一些 hack 增强数据。
hack 我原始对偶的数据:
3 4 1 2
1 2 1 1
1 2 1 2
1 2 1 3
3 2 1 1
3 6