UVa1222

UVa1222

memo[ V ][ R ] = 頂点 V から下で R 個の頂点を選択した時の最小コスト

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

const int inf = 1 << 28;

const int V = 200 + 5;
vector<int> g[V];
int cost[V];
int memo[V][V];
int child[V];

int rec(int node, int require)
{
  int &ret = memo[node][require];
  if (ret != -1) return ret;

  int dp[2][V];
  fill(&dp[0][0], &dp[2 - 1][V], inf);
  dp[0][0] = 0;
  dp[0][child[node]] = cost[node];

  for (int i = 0; i < (int)g[node].size(); ++i) {
    const int src = i % 2;
    const int dst = (i + 1) % 2;
    for (int j = 0; j < (int)V; ++j) {
      if (dp[src][j] == inf) continue;
      dp[dst][j] = min(dp[dst][j], dp[src][j]);
      for (int k = 0; k <= (int)child[g[node][i]] && j + k < V; ++k) {
        dp[dst][j + k] = min(dp[dst][j + k], dp[src][j] + rec(g[node][i], k));
      }
    }
  }

  for (int i = 0; i < (int)V; ++i) {
    memo[node][i] = dp[g[node].size() % 2][i];
  }

  for (int i = V - 1; i; --i) {
    memo[node][i - 1] = min(memo[node][i - 1], memo[node][i]);
  }
  return ret = memo[node][require];
}

int dfs(int node)
{
  child[node] = 1;
  for (int i = 0; i < (int)g[node].size(); ++i) {
    child[node] += dfs(g[node][i]);
  }
  return child[node];
}

int main(int argc, char *argv[])
{
  int node, m;
  while (cin >> node >> m) {
    fill(g, g + V, vector<int>());

    int deg[V];
    fill(deg, deg + V, 0);

    cin.ignore();
    map<string, int> no;
    int size = 0;
    for (int i = 0; i < (int)node; ++i) {
      string s, t, u;
      getline(cin, s);
      istringstream iss(s);
      iss >> t;
      if (no.count(t)) ; else no[t] = size++;
      iss >> cost[no[t]];
      while (iss >> u) {
        if (no.count(u)) ; else no[u] = size++;
        g[no[t]].push_back(no[u]);
        ++deg[no[u]];
      }
    }

    for (int i = 0; i < (int)node; ++i) {
      if (deg[i] == 0) {
        g[size].push_back(i);
      }
    }
    cost[size] = inf;

    dfs(size);
    fill(&memo[0][0], &memo[V - 1][V], -1);
    cout << rec(size, m) << endl;
  }
  return 0;
}