3345 -- Bribing FIPA

POJ

http://poj.org/problem?id=3345
いくつかの木が与えられ，その各ノードにコストが割り振られている．
全部で N 個のノードの中から M 個以上の頂点を選んだときの，コストの和の最小値を求めたい．
ただしあるノードを選んだとき，そのノードのコストで，そのノードを根とする部分木の全ノードを取れるとする．
サンプルだと，Boland を取ることにするとコスト20で Boland と Aland の2つを取れることになる．
1 <= N <= 200, 0 <= M <= N


先日の練習会で聞いた解説の方針で解いた．ただし微妙に DP 表のとり方を変えた．
子ノードの数を価値として単純にナップザック問題として解こうとすると，子ノードを二重に取ってしまってアウト．
とりあえず無限大のコストを持つダミーノードを導入して，これを根とする1つの木にまとめた状態で考える．
各ノードに

dp[i] = このノードを根とする部分木の中から i 個以上取ったときの最小コスト

というような DP 表を持たせ，下のほうから再帰的に埋めていく．
dp[i] の初期値は，部分木のノードの数を m，ノードのコストを c とすると

  • dp[i] = 0 if i == 0
  • dp[i] = c if 1 <= i <= m
  • dp[i] = ∞ otherwise

となる．
あとはナップザック的に各子ノードの DP 表 dp_child について

dp[i] = min{ dp[i-j] + dp_child[j] } (1 <= j <= N)

と更新していけば，ダミーノードの DP 表の M 番目の値が答えとなる．


以下ソース．tree[0] がダミーノード．solve はノード n を根とする部分木のノード数を返している．

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
using namespace std;
static const int INF = 100000000;

struct node
{
  int cost;
  vector<int> children;
  vector<int> dp;
};

int solve(vector<node>& tree, int M, int n = 0)
{
  int value = 1;
  for (vector<int>::const_iterator it(tree[n].children.begin()); it != tree[n].children.end(); ++it) {
    value += solve(tree, M, *it);
  }

  const int N = tree.size();
  vector<int>& dp = tree[n].dp;
  dp.resize(N+1, INF);
  dp[0] = 0;
  for (int i = 1; i <= value; i++) {
    dp[i] = tree[n].cost;
  }
  for (vector<int>::const_iterator it(tree[n].children.begin()); it != tree[n].children.end(); ++it) {
    const vector<int>& dp_child = tree[*it].dp;
    for (int i = value; i >= 0; i--) {
      for (int j = 1; j <= N; j++) {
        if (i-j >= 0) {
          dp[i] = min(dp[i], dp[i-j] + dp_child[j]);
        }
      }
    }
  }
  return value;
}

int main()
{
  string s;
  while (getline(cin, s) && s != "#") {
    int N, M;
    {
      istringstream iss(s);
      iss >> N >> M;
    }
    map<string,int> m;
    vector<node> tree(N+1);
    tree[0].cost = INF;
    vector<bool> owned(N+1, false);
    for (int i = 0; i < N; i++) {
      getline(cin, s);
      istringstream iss(s);
      string t;
      int c;
      iss >> t >> c;
      int id;
      map<string,int>::const_iterator it = m.find(t);
      if (it == m.end()) {
        id = m.size()+1;
        m.insert(make_pair(t, id));
      } else {
        id = it->second;
      }
      tree[id].cost = c;

      while (iss >> t) {
        it = m.find(t);
        int j;
        if (it == m.end()) {
          j = m.size()+1;
          m.insert(make_pair(t, j));
        } else {
          j = it->second;
        }
        tree[id].children.push_back(j);
        owned[j] = true;
      }
    }
    for (int i = 1; i <= N; i++) {
      if (!owned[i]) {
        tree[0].children.push_back(i);
      }
    }
    solve(tree, M);
    cout << tree[0].dp[M] << endl;
  }
  return 0;
}