今天唯一A的题……还是昨天的遗留问题T^T后天晚上就校赛了，一个小破题卡了这么久可怎么好

题目大意：一个人要竞选，需要贿赂别人投选票（真贴近实际），贿赂的人有从属关系，问至少多少钱能买至少m张票

搜这个题的时候看到了01背包的字样，然并卵，虎超超的在草纸上写了一个三维数组真是大错特错，其实分类中【二重dp】的字样是意味着”背包“而已。自己又纠结在有从属关系的表示上orz ，解决方法是：由于dfs时，先遍历子树，再返回根节点，这样，以i为根的子树中的节点可能被多次利用，解决办法就是访问到i时，先开一个tmp数组当前的状态，即dp值，然后访问子树，返回时，先更新tmp值，再用tmp值更新dp值。即 dp值是针对所有情况中的某点最优解，tmp是当前搜索的这个分支上的情况

再有就是字符串的处理sscanf getchar()从寒假就不熟，一直到现在处理字符串还依旧头痛；

背包部分的讲解：

for(int i=m+cnt[u];i>=cnt[u];i--)
    {
        tmp[i]=min(tmp[i-cnt[u]]+w[u],tmp[i]);
        dp[i]=min(dp[i],tmp[i]);
    }

u是当前的根节点，cnt[u]是以u为根的子树节点数即背包的容量（每次做背包都要卡在分辨谁是容量，谁是价值上也是醉）w[u]是贿赂的钱数

居然最后一次WA在了dp数组开小了一半，难道不应该是RE吗╮(╯_╰)╭

/*********
hdu2415
2015.12.27-12.28
0MS 2004K 2210 B G++
*********/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
int n,m,tol;
map<string,int>name;
char str1[204];
int head[10000];
struct node
{
    int from,to,next;
}edge[10000];
void addedge(int a,int b)
{
    edge[tol].from=a;
    edge[tol].to=b;
    edge[tol].next=head[a];
    head[a]=tol++;
}
int w[204],cnt[204],dp[450];
int min(int a,int b)
{
    if(a<b) return a;
    return b;
}
void dfs(int u)
{
    int tmp[400];
    cnt[u]=1;
    memcpy(tmp,dp,sizeof(tmp));
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        dfs(v);
        cnt[u]+=cnt[v];
    }
    for(int i=m+cnt[u];i>=cnt[u];i--)
    {
        tmp[i]=min(tmp[i-cnt[u]]+w[u],tmp[i]);
        dp[i]=min(dp[i],tmp[i]);
    }
}
int main()
{
   // freopen("cin.txt","r",stdin);
    while(gets(str1))
    {
        if(str1[0]=='#') break;
        sscanf(str1,"%d%d",&n,&m);
        name.clear();
        bool is[240];
        memset(is,0,sizeof(is));
        memset(cnt,0,sizeof(cnt));
        memset(dp,0x3f3f3f3f,sizeof(dp));
        memset(head,-1,sizeof(head));
        char str[400];
        int idx=0,ttt;
        tol=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s%d",str,&ttt);
            int k=name[str];
            if(k==0)
            {
                name[str]=++idx;
                k=idx;
            }
            w[k]=ttt;
            //printf("%s:%d   ",str,k);
            char c=getchar();
            while(c==' ')
            {
                scanf("%s",str);
                int l=name[str];
                if(l==0)
                {
                    name[str]=++idx;
                    l=idx;
                }
               // printf("%s:%d   ",str,l);
                addedge(k,l);
                is[l]=1;
                c=getchar();
            }
        }
        dp[0]=0;
        for(int i=1;i<=n;i++) if(!is[i]) dfs(i);
        int ans=0x3f3f3f3f;
        for(int i=m;i<=n*2;i++)
        {
            ans=min(ans,dp[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}