算法:状压 dp
设 $f(i, \ j)$ 表示将 $A$ 组的前 $i$ 个结点都连接完后,$B$ 组结点的连接状态为 $j$ 的情况下的最小连接成本,且保证 $A$ 组的第 $i$ 个结点一定连接于 $j$ 状态所包含的某些 $B$ 组结点。
设 $i$ 与 $B$ 组结点 $k$ 有连接。下文用 $j - k$ 表示 $j \oplus (1 << k)$,即 $j$ 去掉 $k$ 已经被连接后的状态。
-
若 $i$ 与 $k$ 都连接了多个结点,那么删掉 $i, \ k$ 之间连的边后,$i$ 此时至少剩下一个连接的 $B$ 组点,$k$ 此时至少剩下一个连接的 $A$ 组点,也就是说并不影响连通性,同时还将总成本减小了(边权非负)。因此这种情况不可能是最小值,无需考虑。如下图($456 \ A$ 组,$123 \ B$ 组),$i = 4, \ k = 1$:
-
若 $i$ 连接了多个结点,但 $k$ 只连接了 $i$,那删去 $i, \ k$ 这条边,就会得到 $f(i, \ j - k)$ 的状态。
-
若 $i$ 只连接了 $k$,但 $k$ 连接了多个结点,那删去 $i, \ k$ 这条边,就会得到 $f(i - 1, \ j)$ 的状态。
-
若 $i$ 与 $k$ 互相只连接了对方,那删去 $i, \ k$ 这条边,就会得到 $f(i - 1, \ j - k)$ 的状态。
因此可以得到状态转移方程
$$f(i, \ j) = min[f(i, \ j - k), \ f(i - 1, \ j), \ f(i - 1, \ j - k)] + cost[i][k]$$
边界条件:$f(0, \ 0) = 0$,表示 $A$ 组不拿出任何点连边,所以没有成本,其余状态均为非法状态,设为 $+\infty$。
时间复杂度 $O(nm \times 2^m)$
C ++ 代码
constexpr int inf = 1E5;
class Solution {
public:
int connectTwoGroups(vector<vector<int>>& cost) {
int n = cost.size(), m = cost[0].size(), tot = 1 << m;
vector f(n + 1, vector<int>(tot, inf));
f[0][0] = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 0; j < tot; j ++ ) {
for (int k = 0; k < m; k ++ ) {
int w = 1 << k;
if (j & w) {
int x = std::min({f[i][j ^ w], f[i - 1][j], f[i - 1][j ^ w]});
f[i][j] = std::min(f[i][j], x + cost[i - 1][k]);
}
}
}
}
return f[n][tot - 1];
}
};