Function ADS::bipartiteBMatching

Function Documentation

inline std::vector<std::pair<int, int>> ADS::bipartiteBMatching(const std::vector<std::vector<int>> &A, int nr, const std::vector<long long> &capL, const std::vector<long long> &capR)

bipartiteBMatching(): the pairs ( u , v ) of a b-matching of largest size, A[ u ] the nodes on the right adjacent to the node u on the left, u in at most capL[ u ] pairs and v in at most capR[ v ]

Pre:

the items of A in [ 0 , nr ), capL has a place per node on the left and capR nr, all of them >= 0

Post:

the pairs are edges, within the capacities of their ends (audit)