1380. Matching with Weighted Bipartite Graph

Given an n x n matrix where weight[i][j] is the profit of pairing left vertex i with right vertex j, choose a perfect matching that pairs every left vertex with a distinct right vertex. Return the maximum achievable total weight.

Input: A JSON object {"weight": [[...], ...]} describing an n x n matrix.

Output: Return the maximum total weight of a perfect matching.

Examples

Input: {"weight":[[1,2],[3,4]]}
Output: 5
Explanation: Both perfect matchings total 5, so the answer is 5.

Input: {"weight":[[7,1,3],[2,8,5],[4,6,9]]}
Output: 24
Explanation: Matching along the diagonal gives the best total.

Constraints

• 1 <= n <= 15
• 0 <= weight[i][j] <= 10^6

Asked by