# 是否存在諸如使用不同b值進行b匹配的問題？

I'm not sure if it's a standard problem, but it seems this problem is described in Solving the Many to Many assignment problem by improving the Kuhn–Munkres algorithm with backtracking.

(the other closest things I found are https://en.wikipedia.org/wiki/Generalized_assignment_problem and https://link.springer.com/content/pdf/10.1007/BF02190106.pdf, but they are talking about one-to-many assignments).

Anyway, you can solve it using maximum flow. For $$b=1$$ (usual matching) you can check these slides, namely this picture:

I.e. we create auxiliary vertices $$s$$ and $$t$$, create edges $$(s, u)$$ for all $$u$$ in the left part and $$(v, t)$$ for all $$v$$ in the right part. All edges have capacity one. By solving maximum flow on this graph, you'll find maximum matching (Note: you have to find an integral solution, i.e. where flow through each edge is either 1 or 0, but standard maximum flow algorithms will do that).

For $$b>1$$ the graph is the same. The difference is that all edges $$(s,u)$$ have capacity $$b_L$$ and $$(v,t)$$ have capacity $$b_R$$.

If your edges have weights, then you can negate edge weights and solve min-cost max-flow on this graph.