强烈要求增加数据强度!

P3376 【模板】网络最大流

pp_orange @ 2023-04-17 12:00:36

这里数据强度并不是对算法复杂度的测试,一个好的模板题,既要有方便调试的小数据,也要有对极限数据的冲击,但是正确性应当是第一位的,大量错解通过此题数据,这不就是害人吗?

希望好心人@一下相关人士,不是很懂@谁


by bamboo12345 @ 2023-04-17 12:52:22

@pp_orange 可否说明为什么?


by ran_qwq @ 2023-04-17 12:56:23

@pp_orange 能说一下hack数据是怎么样的,以及能hack掉哪些题解吗


by feecle6418 @ 2023-04-17 13:21:01

@pp_orange 请给出具体 hack 数据以及 hack 了什么题解


by pp_orange @ 2023-04-17 13:51:54

@feecle6418 至少添加一个测试点,用于hack未建反向边的代码,无反向边,或反向边建错(或无效)的代码均通过了此题


by pp_orange @ 2023-04-17 13:52:21

@Lovely_Ran 至少添加一个测试点,用于hack未建反向边的代码,无反向边,或反向边建错(或无效)的代码均通过了此题


by pp_orange @ 2023-04-17 13:53:21

@Lovely_Ran 并不是题解有错,但是我个人认为,模板题的数据应当做到精良耐用。


by pp_orange @ 2023-04-17 13:59:46

错解

我把反向边增流操作注释了,一个显然的hack:

8 9 1 4

1 2 1

3 4 1

2 3 1

1 5 1

5 6 1

6 3 1

2 7 1

7 8 1

8 4 1

output:1

answer:2


by hy233 @ 2023-04-17 15:07:47

@pp_orange 是否应当卡掉不加当前流优化的,据说复杂度是错的。


by pp_orange @ 2023-04-17 15:41:59

@hy233 复杂度玄学,这个不太好卡,这也不是什么大问题,大部分网络流的题不过多考虑效率的(前提是图建的是对的而且这个题确实是网络流)


by feecle6418 @ 2023-05-04 18:44:52

@pp_orange done


| 下一页