AOJ 2306 Rabbit Party

問題ページ
Rabbit Party | Aizu Online Judge

考えたこと

• 入力がグラフっぽい
• グラフとしてサンプルを書いてみるけどグラフの知ってるもの(最大安定集合とか)に帰着できない
• DPを考える
• dp[i匹目まで][j匹選んだ] みたいなの
• 今までに選んだうさぎの部分集合を状態に持たないとできる気がしない
• 2^100を持てるわけがない
• DPできる気がしないので貪欲を考える
• i匹選ぶ時の最適な部分集合が単調増加するみたいな
• そんな性質はない
• DPも貪欲もできる気がしない
  -----解説を見た-----
• xとyの友好度が0のとき、xとyを両方取る意味はない
• クリークの大きさの最大値はそんなに大きくない
• 大きさNのクリークではN*(N+1)/2本の辺が必要
• 辺がm本しかないので N*(N+1)/2 <= m = 100 でNが抑えられる
• クリークの要素数は高々14個
• 全探索できる

学び

• クリークの大きさはO(sqrt(m))くらいで抑えられる
• クリークを全列挙する実装

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

const int INF = (1LL<<30);

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int n, m, ans;
int g[105][105];

void dfs(VI &v) {
  if(v.size() >= 2) {
    int tmp = 0;
    REP(i, v.size()) {
      int t = INF;
      REP(j, v.size()) if(i != j) {
        chmin(t, g[v[i]][v[j]]);
      }
      tmp += t;
    }
    chmax(ans, tmp);
  }

  int last = v.back();
  FOR(i, last+1, n) {
    bool ok = true;
    for(int j: v) {
      if(g[i][j] == 0) {
        ok = false;
        break;
      }
    }
    if(ok) {
      v.PB(i);
      dfs(v);
      v.pop_back();
    }
  }
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> m;
  REP(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--,  b--;
    g[a][b] = g[b][a] = c;
  }

  REP(i, n) {
    VI v({i});
    dfs(v);
  }

  cout << ans << endl;

  return 0;
}