建立一個虛點（權(quán)為無窮大），從它到每個入度為 0 的點都連一條邊，然后做樹型DP。
先遞歸算出子結(jié)點的 f 值，然后用背包的方法計算父結(jié)點的 f 值。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-14 12:22:37
File Name: pku3345.cpp
Description:
************************************************************************/
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
typedef long long int64;
const int maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n)
{for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
int n, m;
vector <int> child[300];
vector <string> child_name[300];
string name[300];
int dia[300];
int after[300];
int f[300][300];
int used[300];
int p[300];
int q[300];
int dfs(int x)
{
int ret = 0;
if (used[x]) return after[x];
for (int i = 0; i < child[x].size(); i++)
ret += dfs(child[x][i]);
for (int i = 0; i <= n; i++) p[i] = maxint;
p[0] = 0;
for (int i = 0; i < child[x].size(); i++)
{
for (int j = 0; j <= n; j++) q[j] = maxint;
for (int k = n; k >= 0; k--) if (p[k] != maxint)
{
for (int j = 0; k + j <= n; j++) if (f[child[x][i]][j] != maxint)
q[k + j] <?= p[k] + f[child[x][i]][j];
}
for (int j = 0; j <= n; j++) p[j] <?= q[j];
}
used[x] = 1;
after[x] = ret + 1;
p[after[x]] <?= dia[x];
memcpy(f[x], p, sizeof(p));
return after[x];
}
int in_deg[300];
int main()
{
char s[1000];
while (gets(s), strcmp(s, "#") != 0)
{
if (strcmp(s, "") == 0) continue;
stringstream ss(s);
ss >> n >> m;
for (int i = 0; i < n; i++)
{
child_name[i].clear();
child[i].clear();
char s[100000];
scanf("%s%d", s, &dia[i]);
name[i] = s;
gets(s);
stringstream ss(s);
string t;
while (ss >> t)
child_name[i].push_back(t);
}
memset(in_deg, 0, sizeof(in_deg));
for (int i = 0; i < n; i++)
for (int j = 0; j < child_name[i].size(); j++)
{
for (int k = 0; k < n; k++) if (child_name[i][j] == name[k])
{
child[i].push_back(k);
in_deg[k]++;
break;
}
}
child[n].clear();
for (int i = 0; i < n; i++) if (in_deg[i] == 0)
child[n].push_back(i);
dia[n] = maxint;
memset(used, 0, sizeof(used));
memset(after, 0, sizeof(after));
memset(f, 0, sizeof(f));
dfs(n);
int ans = maxint;
for (int i = m; i <= n; i++) ans <?= f[n][i];
printf("%d\n", ans);
}
return 0;
}