题解 CF1948G【MST with Matching】

非常精彩的转化！

显然，树是二分图。由 König 定理，我们知道：二分图最小点覆盖等于最大匹配。因此枚举点覆盖 \(S\)，则一条边 \((u,v)\) 可以被选择，当且仅当 \(u\in S\lor v\in S\)，在所有可以选择的边上跑最小生成树即可。

我采用的是 Kruskal 算法，时间复杂度为 \(O(2^nn^2\log n)\)，可能略有卡常，可以使用 Prim 算法做到 \(O(2^nn^2)\)。

// Problem: MST with Matching
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1948G
// Memory Limit: 500 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 20, inf = 0x1f1f1f1f;

int n, c, a[N][N], ans = +inf;
vector<tuple<int, int, int>> G;

struct Dsu {
    int fa[N];
    void init(int x) {rep(i, 0, x - 1) fa[i] = i;}
    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    bool merge(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        fa[x] = y;
        return true;
    }
}dsu;

int kruskal() {
    sort(G.begin(), G.end(), [](auto x, auto y) {
        return get<2>(x) < get<2>(y);
    });
    dsu.init(n);
    int rem = n, mst = 0;
    for(auto [u, v, w] : G) {
        if(dsu.merge(u, v)) {
            --rem;
            mst += w;
        }
    }
    return rem == 1 ? mst : +inf;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> c;
    rep(i, 0, n - 1) rep(j, 0, n - 1) cin >> a[i][j];
    rep(S, 1, (1 << n) - 1) {
        G.clear();
        rep(i, 0, n - 1) {
            rep(j, i + 1, n - 1) {
                if(((S >> i) & 1) || ((S >> j) & 1)) {
                    if(a[i][j]) {
                        G.emplace_back(i, j, a[i][j]);
                    }
                }
            }
        }
        chkmin(ans, kruskal() + c * __builtin_popcount(S));
    }
    cout << ans << endl;
    return 0;
}