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 队列优化)