基于N-1次最大流的无向图全局最小割实现性能优化求助

一、直接优化重置容量的操作 #

• 反向撤销增广流，而非全量重置
  每次执行s-t最大流时，记录所有被增广操作修改过的边（即有流量流过的正向/反向边）以及对应的流量值。跑完最大流后，只对这些边执行反向操作：正向边容量 += 流过的流量，反向边容量 -= 流过的流量。这种方式仅处理实际被修改的边，在稀疏图场景下能大幅减少操作量，避免遍历全图所有边的开销。
  实现时可在Dinic算法的增广过程中维护一个日志列表，比如每条记录包含边的索引、修改的流量值，跑完流后遍历日志恢复容量。

• 使用原始容量快照快速复制
  预先保存一份所有边的原始容量数组（或邻接表的原始状态），每次需要重置时，直接将当前残留容量数组复制原始容量的内容。利用底层高效的内存复制操作（如C/C++的memcpy、Python的list.copy()），比循环遍历每条边逐个重置的效率更高。

二、改用更高效的算法框架：Gomory-Hu树 #

你的当前思路是固定源点跑N-1次全图最大流，这本质是暴力枚举所有s-t对的最小割，而Gomory-Hu树算法仅需N-1次最大流，且每次流计算的图规模逐步缩小，从根本上避免了重复重置全图容量的问题：

• 算法核心逻辑：每次选择一对节点s和t，计算s-t的最小割；将t合并到s所在的连通分量中，后续的最大流计算在合并后的简化图上进行；最终构建出的Gomory-Hu树中，树边的权值对应原图的一个最小割，全局最小割即为树中权值最小的边对应的割。
• 这种方式不需要每次恢复全图的原始容量，因为每次迭代的图是基于上一次的合并结果构建的，从根源上减少了不必要的容量重置操作，同时降低了每次最大流计算的图规模。

三、细节优化辅助提升性能 #

• 邻接表存储时，将正向边和反向边绑定存储（比如在邻接表节点中保存反向边的索引），这样在撤销增广或处理残留网络时能快速定位反向边，减少查找开销。
• Dinic算法中复用层级数组、指针数组等数据结构，每次跑完流后仅重置数组内的值，而非重新分配内存，避免频繁内存申请释放的开销。

内容的提问来源于stack exchange，提问作者LFRamos