Skip to main content

Module flow

Module flow 

Source
Expand description

最大流算法模块

包含 Edmonds-Karp、Dinic 等算法

§内存优化

使用稀疏邻接表存储残量图,空间复杂度 O(V+E):

  • edmonds_karp: 使用 HashMap<usize, Vec<(usize, f64)>> 存储残量图
  • dinic: 使用 HashMap<usize, HashMap<usize, f64>> 存储残量
  • push_relabel: 使用 HashMap<usize, HashMap<usize, f64>> 存储残量

对于稠密图(E ≈ V²),可考虑使用邻接矩阵实现(未提供)。

Functions§

dinic
Dinic 最大流算法
edmonds_karp
Edmonds-Karp 最大流算法
push_relabel
Push-Relabel 最大流算法(FIFO 队列优化)