And there should be doc for the public types MatchingMap and StatusMap, of course. (Maybe the later one could be called DecompositionMap or decomposition() could be renamed to status().
The first one of the above functions should also be introduced to the weighted matching classes.
What about using matchingWeight() instead of matchingValue() in the two weighted matching classes?
What about moving MaxWeightedMatching and MaxWeightedPerfectMatching to a separate source file max_weighted_matching.h instead of max_matching.h?