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``。 自建示例 -------- 可以使用一一对应的低成本边覆盖全部点: .. code-block:: text 输入:cost = [[1,3],[4,1]] 输出:2 解释:连接第一组点 0 与第二组点 0,再连接两个编号 1 的点,总成本为 2。 一侧只有一个点时必须连接另一侧全部点: .. code-block:: text 输入:cost = [[2,5,1]] 输出:8 解释:第二组的三个点都需要连接,只能使用三条边,成本之和为 8。