hack 自测题目链接,数据链接(数据链接挂的题目附件链接不知道能不能点开qwq)。
原理是:HLPP 在求最大流的过程中忽略了流守恒性,改为计算超额流,虽然容量和结果都不会超 int 但是每个结点储存的超额流可能会超。
int
但是 Dinic 不会出现这种问题,因为 Dinic 在求解最大流的过程中始终满足流守恒性,并且题目保证了容量和答案都不超过 int 范围,所以 Dinic 不会挂。
UOJ 上好像有类似的 hack,不过 UOJ 的数据范围本来就是要开 long long 的(
long long