TIOJ 2137：殿壬與Tan乙己

TIOJ 2137：殿壬與Tan乙己

題目大意：給你 $n$ 個點與兩個點之間的連接關係，還有每個點的權重 $w_i$，請你求出權重和第 $k$ 小的獨立集。

解法：可以二分搜一個值，看總和小於等於它的數量是不是 $\geq k$，當 $\geq k$ 就 $\text{return}$，時間複雜度 $O(k\times\log(C))$

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 65;

int n, k;
ll g[SIZE], w[SIZE];

bool ok(ll val) {
    int cnt = 1;
    auto dfs = [&](auto dfs, int pos, ll mask, ll sum)->void {
        if ((g[pos] & mask) != mask) return;
        mask |= 1ll << pos;
        sum += w[pos];
        if (sum > val) return;
        cnt++;
        FOR (i, pos + 1, n - 1) {
            if (cnt >= k) return;
            dfs(dfs, i, mask, sum);
        }
    };
    FOR (i, 0, n - 1) dfs(dfs, i, 0, 0);
    return cnt >= k;
}

void solve() {
    cin >> n >> k;
    FOR (i, 0, n - 1) {
        g[i] = 0;
        FOR (j, 0, n - 1) {
            int x;
            cin >> x;
            if (!x) g[i] |= 1ll << j;
        }
    }
    FOR (i, 0, n - 1) cin >> w[i];
    ll l = 0, r = accumulate(w, w + n, 0ll);
    if (!ok(r)) {
        cout << "-1\n";
        return;
    }
    while (l < r) {
        ll mid = (l + r) / 2;
        if (ok(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
}

int main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！