[Medium] CF1948G MST with Matching

简要题意

以邻接矩阵形式给出一个 $n$ 个点的无向带权简单图和一个常数 $c$。

定义这个图的一个生成树的权值，为其边权和加上最大匹配数的 $c$ 倍。输出权值最小值。

$2\leq n\leq 20$。

思路

首先看到最大匹配，大概率要往二分图最大匹配去想，无良出题人应该是不会考带花树之类的东西吧。

然后你迅速发现树是一个二分图（因为我可以按照深度的奇偶性染色），于是可以应用二分图最大匹配的性质。

同时很容易发现 $n\leq 20$ 这个约束条件，应该是暗示我们使用指数级算法枚举一个量，边权和相对容易维护（最小生成树即可），但最大匹配难以维护，可以考虑枚举这个量。

但是最大匹配与边有关，而边有 $O(n^2)$ 条不适合枚举，不妨利用 König 定理，转为最大独立集。

最大独立集是点集，因此可以 $O(2^n)$ 枚举点集，然后排除端点均在独立集的边跑最小生成树算法来更新答案，由于求的是最小值，所以不用刻意限制最大，只需要枚举独立集即可。

使用 Kruskal 算法在稠密图下表现不佳（至少难以通过本题），改为 Prim 算法即可通过。

时间复杂度 $O(2^nn^2)$。

代码

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;

using i64 = long long;
const int N = 25;
int n, c, a[N][N], b[N][N], dis[N];
bool vis[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cin >> a[i][j];
    }
    i64 ans = LLONG_MAX;
    dis[0] = INT_MAX; vis[1] = 1;
    for(int S=0;S<(1<<n);S++){
        int cnt = 0;
        i64 sum = 0; bool flag = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) b[i][j] = (((S >> (i - 1)) & 1) && ((S >> (j - 1)) & 1)) ? 0 : a[i][j];
        }
        fill(vis + 2, vis + n + 1, 0);
        fill(dis + 2, dis + n + 1, INT_MAX);
        for(int i=1;i<=n;i++){
            if(b[1][i]) dis[i] = b[1][i];
        }
        for(int i=1;i<n;i++){
            int x = 0;
            for(int j=1;j<=n;j++){
                if(!vis[j] && dis[j] < dis[x]) x = j;
            }
            if(!x){ flag = 0; break; }
            vis[x] = 1, sum += dis[x];
            for(int j=1;j<=n;j++){
                if(!vis[j] && b[x][j]) dis[j] = min(dis[j], b[x][j]);
            }
        }
        if(flag) ans = min(ans, sum + 1ll * c * (n - __builtin_popcount(S)));
    }
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan