TLE が厳しかった...

問題概要

頂点数 $N$ の単純無向グラフ $G$ が与えられる (連結とは限らない)。各頂点 $v$ には重み $B_{v}$ がついている。

頂点 1 を含む $G$ の安定集合をすべて考えたときの、安定集合中の頂点の重もの総和の最大値を求めよ。

制約

$1 \le N \le 40$
$0 \le B_{v} \le 1000$

考えたこと

重みがなければ、「最大安定集合ライブラリ」を貼るだけ。重みがあっても、本当はこれをちょっと改良するだけなんだけど、その改良が面倒。

なので、半分全列挙で解くことにした (想定解法でもある模様)。頂点 1 以外の頂点を半分ずつに分けて (left, right とする)、bit DP によって以下の値を求めた。

left[ S ] := 頂点部分集合 left の部分集合 S に含まれる頂点のみで構成される安定集合の重みの最大値
right[ T ] := 頂点部分集合 right の部分集合 T に含まれる頂点のみで構成される安定集合の重みの最大値

注意点として、頂点 1 は選ぶことが確定しているので、頂点 1 と隣接している頂点については、あらかじめすべて除外して考えるようにした。

この DP と、半分全列挙に要する計算量はそれぞれ $O(N^{2}2^{\frac{N}{2}})$ となる。

TLE が厳しいので、頂点 v に隣接する頂点集合を表すビットを前処理するなどの工夫を行った。これで実際上は $O(N 2^{\frac{N}{2}})$ という感じになる (理論的にはならない)。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using Graph = vector<vector<int>>;
vector<long long> half(const Graph &G, const vector<bool> &can, const vector<long long> &W, int left, int right) {
    int num = right - left;
    vector<long long> dp(1<<num, 0);
    vector<int> ng(num, 0);
    for (int v = left; v < right; ++v) {
        for (auto u : G[v]) if (u >= left && u < right) ng[v-left] |= 1<<(u-left);
    }
    for (int bit = 1; bit < (1<<num); ++bit) {
        for (int v = left; v < right; ++v) {
            if (!(bit & (1<<(v-left)))) continue;
            int nbit = bit & ~(1<<(v-left));
            chmax(dp[bit], dp[nbit]);
            if (can[v]) {
                nbit &= ~ng[v-left];
                chmax(dp[bit], dp[nbit] + W[v]);
            }
        }
    }
    return dp;
}

long long solve(const Graph &G, const vector<bool> &can, const vector<long long> &W) {
    int N = G.size();
    int mid = (N+1)/2;
    const auto &left = half(G, can, W, 1, mid);
    const auto &right = half(G, can, W, mid, N);
    vector<int> ng(N, 0);
    for (int v = 1; v < mid; ++v) {
        for (auto u : G[v]) {
            if (u >= mid) ng[v] |= 1<<(u-mid);
        }
    }
    long long res = 0;
    for (int bit = 0; bit < (1<<(mid-1)); ++bit) {
        int rbit = (1<<(N-mid)) - 1;
        for (int v = 1; v < mid; ++v) {
            if (!(bit & (1<<(v-1)))) continue;
            rbit &= ~ng[v];
        }
        chmax(res, left[bit] + right[rbit]);
    }
    return res + W[0];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    while (cin >> N, N) {
        map<string,int> ma;
        vector<long long> B(N);
        vector<vector<string>> adj(N);
        for (int i = 0; i < N; ++i) {
            string str; cin >> str;
            ma[str] = i;
            cin >> B[i];
            int num;
            cin >> num;
            adj[i].resize(num);
            for (int j = 0; j < num; ++j) cin >> adj[i][j];
        }
        Graph G(N);
        vector<bool> can(N, true);
        for (int i = 1; i < N; ++i) {
            for (auto str : adj[i]) {
                if (ma[str] != 0) G[i].push_back(ma[str]);
                else can[i] = false;
            }
        }
        cout << solve(G, can, B) << endl;
    }
}