因为贡献是两个之和，考虑固定下一个，求解另一个的最优。
\(\text{MST}\) 似乎找不到什么好的办法固定，便考虑固定下最大匹配。
对于树的最大匹配，考虑到因为树也是二分图，所以树的最大匹配 \(=\) 最小点覆盖。
考虑如果知道了最小点覆盖内的点，那就说明如果一条边两个端点都不在点集中，是不可能出现在这个对应的树中的，因为没有被覆盖。
于是把至少有一个端点在点集中的边集拎出来跑 \(\text{MST}\) 即可。
因为 \(n\) 的规模较小，可以直接枚举最小点覆盖的点集求解。
时间复杂度 \(O(n^2\log n^2 + 2^nn^2)\)。
代码
#include<bits/stdc++.h>
const int maxn = 20 + 5, maxm = maxn * maxn;
struct Eg {int u, v, w;};
std::vector<Eg> E;
int fa[maxn];
int getfa(int x) {return fa[x] == x ? x : (fa[x] = getfa(fa[x]));}
inline bool merge(int x, int y) {x = getfa(x), y = getfa(y); return x == y ? false : (fa[x] = y, true);}
int main() {
int n, c; scanf("%d%d", &n, &c);
for (int i = 0; i < n; i++) for (int j = 0, x; j < n; j++) {
scanf("%d", &x);
x && (E.push_back({i, j, x}), 1);
}
std::sort(E.begin(), E.end(), [&](const auto &a, const auto &b) {return a.w < b.w;});
long long ans = LLONG_MAX;
for (int s = 0; s < (1 << n); s++) {
long long tot = 1ll * c * __builtin_popcount(s);
std::iota(fa, fa + n, 0);
int cnt = n;
for (auto _ : E) (s & (1 << _.u | 1 << _.v)) && merge(_.u, _.v) && (cnt--, tot += _.w);
cnt == 1 && (ans = std::min(ans, tot));
}
printf("%lld\n", ans);
return 0;
}