关于复杂度
查看原帖
关于复杂度
429147
hxhhxh楼主2024/1/16 16:58

rt,我在网上没有找到什么关于这题网络流的复杂度分析(都说网络流玄学,O(能过)O(\text{能过})),也没有找到相关 hack。

正常实现的 Dinic 网络流在经特殊构造的图上的复杂度上界是 O(n2m)O(n^2m) 的,对于这题的数据范围而言显然不能通过。而这题的网络流图比较特殊,能否把它分析出一个能通过的复杂度或常数或者说卡掉它?

2024/1/16 16:58
加载中...