1595. Minimum Cost to Connect Two Groups of Points

题目信息

题号:

1595

难度:

Hard

主题:

二分图、状态压缩、动态规划

原题:

LeetCode 1595

重点:

可在两组点之间选择任意多条边,每个点至少连接一次;边 i-j 成本为 cost[i][j],最小化总成本

题目重述

有两组点,第一组大小为 size1,第二组大小为 size2。矩阵 cost[i][j] 表示连接第一组点 i 与第二组点 j 的成本。

请选择若干跨组连接,使两组中的每个点都至少与另一组中的一个点相连,并返回最小总成本。

1 <= size1, size2 <= 12,1 <= cost[i][j] <= 100。

自建示例

可以使用一一对应的低成本边覆盖全部点:

输入:cost = [[1,3],[4,1]]
输出:2
解释:连接第一组点 0 与第二组点 0,再连接两个编号 1 的点,总成本为 2。

一侧只有一个点时必须连接另一侧全部点:

输入:cost = [[2,5,1]]
输出:8
解释:第二组的三个点都需要连接,只能使用三条边,成本之和为 8。