AOJ 2306 Rabbit Party - mayoko’s diary

問題

n 匹のウサギがパーティーをする。各ウサギには友達度が定義されている(これが正の値を取るのは高々 m 個)。
ウサギ i がパーティーに参加した際の満足度は, パーティーに参加したウサギのうち, 友達度が最も低いものとのそれに等しく, パーティー全体の満足度は, パーティーに参加したウサギの満足度の和である。これを最大化せよ。

解法

a, b の友達度が 0 の場合, 少なくとも a と b のどちらかはパーティーに参加しないほうが得です(a と b の満足度はどちらも 0 になるのでうまみがないし, ほかのウサギにとっても損はあっても得はない)。
つまり, パーティー全体の満足度を最大化する組み合わせにおいて,

任意の (i, j) について, i と j の友達度は正

ということが成り立っているはずです。m は 100 と小さいので, これを満たす集合は, どんなに大きくても 14 にしかなりません。それを考えると, 上記の条件を満たす, ということだけ保つように dfs すれば十分高速に答えを求められそうな気がします。

試しに書いてみると, 通りました。

const int MAXN = 111;
const int INF = 1e9;
int mat[MAXN][MAXN];
int ans;
int n, m;

void dfs(vector<int>& v) {
    int sz = v.size();
    if (v.size() > 1) {
        int tmp = 0;
        for (int i = 0; i < sz; i++) {
            int mini = INF;
            for (int j = 0; j < sz; j++) if (j != i) {
                mini = min(mini, mat[v[i]][v[j]]);
            }
            tmp += mini;
        }
        ans = max(ans, tmp);
    }
    int last = v.back();
    for (int i = last+1; i < n; i++) {
        bool ok = true;
        for (int j = 0; j < sz; j++) {
            if (!mat[i][v[j]]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            v.push_back(i);
            dfs(v);
            v.pop_back();
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, f;
        cin >> u >> v >> f;
        u--; v--;
        mat[u][v] = mat[v][u] = f;
    }
    ans = 0;
    for (int i = 0; i < n; i++) {
        vector<int> v(1, i);
        dfs(v);
    }
    cout << ans << endl;
    return 0;
}