POJ 3345-Bribing FIPA（树状背包）

题意：

有n个国家投票，要得到一个国家的投票有一定的花费，如果给到一个国家的票同时也得到了它所有附属国的票，给出国家关系树，求至少得到m票的最小花费。

分析：基础树状背包，dp[i][j],以i为根的子树得j票的最小花费，该题输入有点恶心。

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0xfffffff;

const int mod =  ;

int dp[][],v[];

vector<int>e[];

map<string,int>ma;

int n,m;

int dfs(int root){

    int i,j,k,son;

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

        dp[root][i]=INF;

    dp[root][]=;

    int num=;

    for(i=;i<e[root].size();++i){

         son=e[root][i];

        num+=dfs(son);//统计节点的个数

        for(j=n;j>=;j--)

        for(k=;k<=j;++k)

        dp[root][j]=min(dp[root][j],dp[root][j-k]+dp[son][k]);

    }

    dp[root][num]=min(dp[root][num],v[root]);//取较小的一个，v[root]选根节点，得所有子树的票，需要的花费。

    return num;

}

int main()

{

    char name[];

    int par[];

   while( gets(name) && name[] != '#') {

        sscanf(name, "%d%d", &n,&m);

        memset(par,,sizeof(par));

        ma.clear();

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

            e[i].clear();

        int index=;

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

           scanf("%s",name);

            if(ma.find(name)==ma.end()){

            ma[name]=++index;

            }

            int tmp=ma[name];

            scanf("%d",&v[tmp]);

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

             scanf("%s",name);

            if(ma.find(name)==ma.end())

            ma[name]=++index;

            par[ma[name]]=;

             e[tmp].push_back(ma[name]);

           }

        }

         v[]=INF;

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

            if(!par[i])

            e[].push_back(i);

        }

        dfs();

        int minv=INF;

        for(int i=m;i<=n;++i){

            minv=min(minv,dp[][i]);

        }

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

    }

return ;

}