mcmf

此软件包用于解决 最小成本最大流问题 的实例。它使用来自 LEMON 图优化库的网状简单算法。

许多问题是最小成本最大流的特殊情况，包括最大流、单源最短路径以及在二分图上的最大权匹配。

因此，此软件包可以解决上述所有问题，尽管它可能不如专用算法高效。

请参阅 文档。

示例

use mcmf::{GraphBuilder, Vertex, Cost, Capacity};
let (cost, paths) = GraphBuilder::new()
    .add_edge(Vertex::Source, "Vancouver", Capacity(2), Cost(0))
    .add_edge("Vancouver", "Toronto", Capacity(2), Cost(100))
    .add_edge("Toronto", "Halifax", Capacity(1), Cost(150))
    .add_edge("Vancouver", "Halifax", Capacity(5), Cost(400))
    .add_edge("Halifax", Vertex::Sink, Capacity(2), Cost(0))
    .mcmf();
assert_eq!(cost, 650);
assert_eq!(cost, paths.iter().map(|path| path.cost()).sum());
assert_eq!(paths.len(), 2);
assert!(
    paths[0].vertices() == vec![
        &Vertex::Source,
        &Vertex::Node("Vancouver"),
        &Vertex::Node("Halifax"),
        &Vertex::Sink]);
assert!(
    paths[1].vertices() == vec![
        &Vertex::Source,
        &Vertex::Node("Vancouver"),
        &Vertex::Node("Toronto"),
        &Vertex::Node("Halifax"),
        &Vertex::Sink]);