Minimum Cost to Connect Two Groups
Two groups of services must be fully cross-wired: every service in each group needs at least one link to the other group. A cost matrix gives the price of each cross-link. Minimize total cost.
Problem
Given two groups of sizes m and n (m <= n is not guaranteed) and a cost matrix cost where cost[i][j] is the price of connecting point i of group 1 to point j of group 2, connect the groups so that every point in both groups has at least one connection. Return the minimum total connection cost.
Input
cost: an m x n matrix of non-negative integers; group 1 has m points, group 2 has n points.
Output
An integer: the minimum total cost to connect both groups.
Constraints
- 1 <= m, n <= 12
- 0 <= cost[i][j] <= 100
Examples
Example 1
Input
cost = [[15,96],[36,2]]
Output
17
Connect (0->0)=15 and (1->1)=2 for 17; both groups fully covered.
Example 2
Input
cost = [[1,3,5],[4,1,1],[1,5,3]]
Output
4
A cover using cheap edges totals 4.