1595. Minimum Cost to Connect Two Groups of Points¶
题目信息¶
- 题号:
1595
- 难度:
Hard
- 主题:
二分图、状态压缩、动态规划
- 原题:
- 重点:
可在两组点之间选择任意多条边,每个点至少连接一次;边
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。