[题目链接]
http://poj.org/problem?id=3345
[算法]
树形背包
[代码]
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 210 const int INF = 2e9; int i,j,k,root,n,m,tot,u,v,x,ans; int size[MAXN],fa[MAXN],val[MAXN]; int f[MAXN][MAXN]; char s[MAXN]; map< string,int > mp; vector< int > e[MAXN]; inline void dp(int u) { int i,j,k,v; f[u][0] = 0; size[u] = 1; for (i = 0; i < (int)e[u].size(); i++) { v = e[u][i]; dp(v); size[u] += size[v]; for (j = size[u]; j >= 0; j--) { for (k = 0; k <= size[v]; k++) { f[u][j] = min(f[u][j],f[u][j - k] + f[v][k]); } } } if (u != root) f[u][size[u]] = min(f[u][size[u]],val[u]); } int main() { while (scanf("%s",&s) != EOF && strcmp(s,"#") != 0) { scanf("%d",&m); n = 0; for (i = 0; s[i] != ' '; i++) n = n * 10 + s[i] - '0'; tot = 0; mp.clear(); memset(val,0,sizeof(val)); memset(fa,0,sizeof(fa)); for (i = 0; i <= n; i++) e[i].clear(); for (i = 1; i <= n; i++) { scanf("%s%d",&s,&x); if (!mp[s]) mp[s] = ++tot; u = mp[s]; val[u] = x; while (getchar() != ' ') { scanf("%s",&s); if (!mp[s]) mp[s] = ++tot; v = mp[s]; e[u].push_back(v); fa[v] = u; } } root = 0; for (i = 1; i <= n; i++) { if (!fa[i]) e[root].push_back(i); } memset(size,0,sizeof(size)); memset(f,0x3f,sizeof(f)); dp(root); ans = INF; for (i = m; i <= n; i++) ans = min(ans,f[0][i]); printf("%d ",ans); } return 0; }