1595. 连通两组点的最小成本

1595.连通两组点的最小成本

题目描述：

给出两组点，其中第一组有 $size1$ 个点，第二组有 $size2$ 个点，并且 $size1 \ge size2$ 。任意两点间的连接成本为 $cost[i][j]$ 。如果两组中的每个点都与另一组中的一个或多个点连接，则称两组点是连通的。返回连通两组点所需的最小成本。

数据范围：

$1\le size1, size2 \le 12; size1 \ge size2$

题解：

状压dp：

使用 $dp[i][s]$ 表示第一组中前 $i$ 个点已经全部连通，并且第二组中的点的状态为 $j$ 时的最小成本。初始 $dp[0][0] = 0$ ，其余的全为无穷大。答案就是 $dp[n][(1 << m) - 1]$ 。

对于 $dp[i][j]$ 考虑枚举第二组中的每个点 $k$ ，如果 $k$ 和 $i$ 有边，分成三种情况讨论：

• $i,k$ 多对一：那么 dp[i][j] = dp[i - 1][j] + c，
• $i,k$ 一对多：那么 dp[i][j] = dp[i][j ^ k] + c，
• $i,k$ 一对一：那么 dp[i][j] = min(dp[i-1][j ^ k], dp[i][j^k]) + c

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 13;
    const static int maxm = (1 << 12);
    int dp[maxn][maxm];
    int connectTwoGroups(vector<vector<int>> &cost)
    {
        int n = cost.size(), m = cost[0].size();
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;
        // dp[i][s]
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < (1 << m); ++j)
            {
                for (int k = 0; k < m; ++k)
                {
                    if ((j >> k) & 1)
                    {
                        int c = cost[i - 1][k];
                        dp[i][j] = min(dp[i][j], dp[i - 1][j] + c);
                        dp[i][j] = min(dp[i][j], dp[i][j ^ (1 << k)] + c);
                        dp[i][j] = min(dp[i][j], dp[i - 1][j ^ (1 << k)] + c);
                    }
                }
            }
        }
        return dp[n][(1 << m) - 1];
    }
};