minimum-cost-to-connect-two-groups-of-points

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two groups of points where the first group has <code>size1</code> points, the second group has <code>size2</code> points, and <code>size1 &gt;= size2</code>.

The <code>cost</code> of the connection between any two points are given in an <code>size1 x size2</code> matrix where <code>cost[i][j]</code> is the cost of connecting point <code>i</code> of the first group and point <code>j</code> of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.

Return the minimum cost it takes to connect the two groups.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/03/ex1.jpg" style="width: 322px; height: 243px;" />
<pre>
Input: cost = [[15, 96], [36, 2]]
Output: 17
Explanation: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/03/ex2.jpg" style="width: 322px; height: 403px;" />
<pre>
Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
Output: 4
Explanation: The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.
</pre>

Example 3:

<pre>
Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
Output: 10
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>size1 == cost.length</code></li>
	<li><code>size2 == cost[i].length</code></li>
	<li><code>1 &lt;= size1, size2 &lt;= 12</code></li>
	<li><code>size1 &gt;= size2</code></li>
	<li><code>0 &lt;= cost[i][j] &lt;= 100</code></li>
</ul>

connectTwoGroups

Minimum Cost to Connect Two Groups of Points

Bit Manipulation

Array

Dynamic Programming

Bitmask

Matrix

给你两组点，其中第一组中有 <code>size1</code> 个点，第二组中有 <code>size2</code> 个点，且 <code>size1 &gt;= size2</code> 。

任意两点间的连接成本 <code>cost</code> 由大小为 <code>size1 x size2</code> 矩阵给出，其中 <code>cost[i][j]</code> 是第一组中的点 <code>i</code> 和第二组中的点 <code>j</code> 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/20/ex1.jpg" style="height: 243px; width: 322px;">

<pre>输入：cost = [[15, 96], [36, 2]]
输出：17
解释：连通两组点的最佳方法是：
1--A
2--B
总成本为 17 。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/20/ex2.jpg" style="height: 403px; width: 322px;">

<pre>输入：cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
输出：4
解释：连通两组点的最佳方法是：
1--A
2--B
2--C
3--A
最小成本为 4 。
请注意，虽然有多个点连接到第一组中的点 2 和第二组中的点 A ，但由于题目并不限制连接点的数目，所以只需要关心最低总成本。</pre>

示例 3：

<pre>输入：cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
输出：10
</pre>

&nbsp;

提示：

<ul>
	<li><code>size1 == cost.length</code></li>
	<li><code>size2 == cost[i].length</code></li>
	<li><code>1 &lt;= size1, size2 &lt;= 12</code></li>
	<li><code>size1 &gt;=&nbsp;size2</code></li>
	<li><code>0 &lt;= cost[i][j] &lt;= 100</code></li>
</ul>