[POJ 3345] Bribing FIPA

[题目链接]
[算法]
树形背包
[代码]
#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][] = ;

        size[u] = ;

        for (i = ; i < (int)e[u].size(); i++)

        {

                v = e[u][i];

                dp(v);

                size[u] += size[v];

                for (j = size[u]; j >= ; j--)

                {

                        for (k = ; 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,"#") != )

        {

                scanf("%d",&m);

                n = ;

                for (i = ; s[i] != '\0'; i++) n = n *  + s[i] - '';

                tot = ;

                mp.clear();

                memset(val,,sizeof(val));

                memset(fa,,sizeof(fa));

                for (i = ; i <= n; i++) e[i].clear();

                for (i = ; i <= n; i++)

                {

                        scanf("%s%d",&s,&x);

                        if (!mp[s]) mp[s] = ++tot;

                        u = mp[s];

                        val[u] = x;

                        while (getchar() != '\n')

                        {

                                scanf("%s",&s);

                                if (!mp[s]) mp[s] = ++tot;

                                v = mp[s];

                                e[u].push_back(v);

                                fa[v] = u;

                        }

                }

                root = ;

                for (i = ; i <= n; i++)

                {

                        if (!fa[i])

                                e[root].push_back(i);

                }

                memset(size,,sizeof(size));

                memset(f,0x3f,sizeof(f));

                dp(root);

                ans = INF;

                for (i = m; i <= n; i++) ans = min(ans,f[][i]);

                printf("%d\n",ans);

        }

        return ;

}