SRM 571 Div2 1000 MagicMoleculeEasy

問題概要
グラフG(V, E)が与えられる。
各ノードには得点p[i]が割り振られている。
Vの中からk個のノードを選びたい。ただし、ノードv-w間にエッジが存在するとき、v, wのいずれかは必ず選ばなければならない。
選ばれたノードの得点の和の最大値を求めよ。

解法
あるエッジ(v, w)に注目すると、
vが選ばれなかった場合、wは必ず選ばなければならない。
wが選ばれなかった場合、vは必ず選ばなければならない。
という2パターンの分岐が発生する。どちらかを選ぶとkは1つ減る。

つまり全列挙を行っても高々2^k程度のパターンしかなく全列挙が可能。
ノードを選ぶ・選ばないではなく、エッジで結ばれるノードのどちらを選ぶかで状態を考えるという発想力が必要な問題。

今回の問題のように、入力のサイズ（=今回はグラフのサイズ）とは関係のないパラメータkに対してのみ指数時間かかるアルゴリズムをFPT（Fixed Parameter Tractable）アルゴリズムと呼ぶらしい。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int n;
bool conn[50][50];
int point[50];
vector<pair<int, int> > es;

int solve(int k, set<int> &s) {
  int p;
  for (p = 0; p < es.size(); p++) {
    if (!s.count(es[p].first) && !s.count(es[p].second))
      break;
  }

  if (p == es.size()) {
    int ret = 0;
    vector<int> ps;
    REP (i, n) {
      if (s.count(i))
        ret += point[i];
      else
        ps.push_back(point[i]);
    }
    sort(ps.rbegin(), ps.rend());
    REP (i, k) ret += ps[i];
    return ret;
  }

  if (es.size() - p > k * n)
    return -1;

  int ret = -1;
  int x = es[p].first;
  int y = es[p].second;

  s.insert(x);
  ret = max(ret, solve(k-1, s));
  s.erase(x);

  s.insert(y);
  ret = max(ret, solve(k-1, s));
  s.erase(y);
  
  return ret;
}

class MagicMoleculeEasy {
public:
  int maxMagicPower(vector<int> magicPower, vector<string> magicBond, int k) {
    n = magicPower.size();
    memset(conn, 0, sizeof(conn));
    REP (i, n) REP (j, n) conn[i][j] = magicBond[i][j] == 'Y';
    REP (i, n) point[i] = magicPower[i];
    es.clear();
    REP (i, n) REP (j, i) if (magicBond[i][j] == 'Y') es.push_back(make_pair(i, j));
    set<int> s;
    return solve(k, s);
  }
};