Aizu Online Judge 2306 - Rabbit Party - fooractalの競プロ日記

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2306

うさぎは何匹かの他のうさぎをパーティに招待しようとしています。うさぎの間ではお互いに友達であるようなペアがあり、その仲良し度は $f$ で表されます。友達関係でないうさぎ同士は仲良し度が0であるとみなされます。
またあるうさぎをパーティに招待した時、そのうさぎの楽しかった度はパーティすべての参加者との間の仲良し度のうち最小の値となります。
$n$ 匹のうさぎと $m$ 組の仲良しペアの情報が与えられるので、その情報をもとにパーティの参加者の楽しかった度の総和を最大化してください。

解法

うさぎを頂点、仲良しの関係を辺とする無向グラフとして問題を考えます。
ここである頂点の集合 $S$ に対して、新たに頂点 $v$ を付け加えてみます。もし $S$ の中に $v$ と隣接しない頂点が存在する場合、その頂点によるコストは0, また付け加える頂点のコストも0です。また、 $v$ を付け加えることによって既存の頂点の寄与するコストが増えるということは最小の辺のコストが選択されるという条件によりありえません。したがって辺を繋いだ時に完全グラフとなるような頂点の集合が最適解となります。
$n$ が100なので頂点数100の完全グラフまで探索しようとすると一見間に合わないように思えますが、辺の数が100と少ないです。頂点数 $x$ のグラフが完全グラフとなるためには辺が $x \times (x - 1) \div 2$ 本必要になるため、 $(15 \times 14) \div 2 = 105$ より頂点数15の部分グラフについて調べればいいことがわかります。
あとは適当に枝刈りしながらすべての完全部分グラフを全探索すれば通ります。

ソースコード

#include <iostream>
#include <vector>
using namespace std;

const int kINF = 1 << 28;
const int kMAX_N = 110;

int n, m;

int graph[kMAX_N][kMAX_N];

// 頂点数target_sizeの完全グラフとなるような部分グラフを調べる
int DFS(vector<int>& subgraph, int target_size, int node_id) {
    int result = 0;

    if (subgraph.size() == target_size) {
        // 調べている(完全)部分グラフのコストを計算する
        for (int one_i = 0; one_i < target_size; one_i++) {
            int edge_cost = kINF;

            for (int ano_i = 0; ano_i < target_size; ano_i++) {
                if (one_i == ano_i) continue;

                int one = subgraph[one_i],
                    ano = subgraph[ano_i];
                edge_cost = min(edge_cost, graph[one][ano]);
            }
            result += edge_cost;
        }
        return result;
    }
    // 枝刈り
    if (n - node_id < target_size - subgraph.size()) {
        return result;
    }

    for (int node = node_id; node < n; node++) {
        // 頂点を付け加えることによって完全グラフであることが保たれるか確かめる
        bool is_perfect = true;
        for (int i = 0; i < subgraph.size(); i++) {
            is_perfect = is_perfect && graph[node][subgraph[i]];
        }
        if (!is_perfect) continue;

        subgraph.push_back(node);
        result = max(result, DFS(subgraph, target_size, node + 1));
        subgraph.pop_back();
    }

    return result;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, f;
        cin >> u >> v >> f;
        graph[u - 1][v - 1] = graph[v - 1][u - 1] = f;
    }

    int ans = 0;
    // (15 * 14) / 2 = 105 より頂点数15の部分グラフまでを調べれば十分
    for (int target_size = 2; target_size <= 15; target_size++) {
        vector<int> subgraph;
        ans = max(ans, DFS(subgraph, target_size, 0));
    }
    cout << ans << endl;

    return 0;
}

感想

普段頂点数で制約を判断していたので、気づくのに時間がかかりました。ポケモンGoリリース翌日の記事です。