wa
#pragma warning(disable:4996) #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<iostream> #include<map> using namespace std; const int INF=0x3f3f3f3f; int n, M, dp[205][205], k[205], cost[205], vist[205]; vector<int>tree[205]; map<string, int>index; void init(int n) { index.clear(); for (int i = 0; i <= n; i++) { cost[i] = INF; vist[i] = 0; tree[i].clear(); } } void dfs(int p) { int len = tree[p].size(); dp[p][0] = 0; k[p] = 0; vist[p] = 1; for (int i = 1; i <= n; i++) dp[p][i] = cost[p]; for (int i = 0; i<len; i++) { int son = tree[p][i]; if (vist[son]) continue; dfs(son); k[p] += k[son]; for (int m = k[p]; m>0; m--) for (int s = 1; s <= k[son] && s <= m; s++) if (dp[p][m]>dp[p][m - s] + dp[son][s]) dp[p][m] = dp[p][m - s] + dp[son][s]; } dp[p][++k[p]] = cost[p]; } int main() { char nn[5], name[105]; int c, i; while (scanf("%s", nn)>0 && strcmp(nn, "#") != 0) { scanf("%d", &M); n = 0; for (i = 0; nn[i] != '\0'; i++) n = n * 10 + nn[i] - '0'; init(n); int ind = 0; for (i = 1; i <= n; i++) { scanf("%s%d", name, &c); if (index[name] == 0) { ind++; index[name] = ind; } int fath = index[name], son; cost[fath] = c; while (getchar() != '\n') { scanf("%s", name); if (index[name] == 0) { ind++; index[name] = ind; } son = index[name]; vist[son] = 1; tree[fath].push_back(son); } } cost[0] = 0; for (i = 1; i <= n; i++) { if (vist[i] == 0) cost[0] += cost[i], tree[0].push_back(i); vist[i] = 0; } dfs(0); int ans = dp[0][M]; for (i = M + 1; i <= n; i++) if (dp[0][i]<ans) ans = dp[0][i]; printf("%d\n", ans); } }