mwmatching

通用图中的加权最大匹配。

这是 Joris van Rantwijk 的一个 Python 程序的 Rust 重实现。大部分注释都是直接从那个版本取的。对于原始代码，请访问 http://jorisvr.nl/article/maximum-matching.

在给定的 "edges" 的通用无向加权图中计算最大权重匹配。
通用用法

  let mates = Matching::new(edges).solve();

或

  let mates = Matching::new(edges).max_cardinality().solve();

如果使用 "max_cardinality()"，则只考虑最大基数匹配作为解决方案。

Edges 是一个表示顶点 i 和顶点 j 之间无向边（权重 wt）的元组序列 (i, j, wt)。目前，wt 必须是 i32。任何两个顶点之间最多有一条边；没有顶点有指向自身的边。顶点由连续的非负整数（usize）标识。

返回一个列表 "mates"，如果顶点 i 匹配到顶点 j，则 mates[i] == j；如果顶点 i 未匹配，则 mates[i] == SENTINEL，其中 SENTINEL 是 usize::max_value()。