POJ3345 - 树型DP....要细心啊....T_T..

这题卡了将近一天....感觉好没状态啊...开始的DP状态转移还搞错了...搞得自己头都大了...中午看了集《全开Girl》..眼泪都要哗哗了....再来敲...居然给过了....好吧...

题目的意思就是有N个城市...我需要M个城市支持..每个城市都有支持所需要的费用....有些城市有隶属关系...那只要将老大的钱给了..隶属的城市就自动过来了....题目中有说每个城市最多隶属一个城市...没有形成环的情况...所以这就是一棵树...呃...不对...只是一片森林...因为可能有N个根节点....但我们可以把森林上端加一个超级根..连向所有跟...这个森林就成了一棵树..建图应该不要太过考虑...差不多是赤果果的...

输入很恶心.....只能一次读一行再来判断...要转整型..要转string的...手动来...而且一个点的孩子有多少个也不给出...也要手动来计数下...我的input就写了无比的长...eegache..

主要问题是如何来DP... 感觉这个DP有一点背包的思想...dp [ h ] [ k ] 代表第 h 号点这课子树有 k 个城市拉拢了的最少代价... 那么...

dp [ h ] [ i+ a[p] ] = Min (dp [ h ] [ i ]+ dp [ p ] [ a[p] ] ) < p是其所有孩子节点..a[p]代表p这课子树的节点数 >

大致思想就是这样...写的时候要多多注意细节..譬如...每次更新dp[ h ] 时不要直接更新...这样会造成重复更新....可以先用一个数组temp来记录dp[ h ]的更新情况...更新完后再将temp的值赋给dp [ h ]...

Program:

#include<iostream>
#include<map>
#include<string.h>
#include<stdio.h>
#include<queue>
using namespace std;
map<string,int> mymap;
int n,m,a[205],father[205],totol[205],son[205],temp[205];
char s[1000];
queue<int> myqueue;
void input()
{
        int x,p,l,k,Num,g,i; 
        string str;
        i=0; n=0;
        while (s[i]!=' ') n=n*10+s[i++]-'0'; 
        i++; m=0;
        while (s[i]>='0' && s[i]<='9' )  m=m*10+s[i++]-'0'; 
        memset(father,0,sizeof(father));
        mymap.clear();
        p=0;  
        for (i=1;i<=n;i++)
        {
            gets(s); l=strlen(s);
            str="";  k=0;
            while (s[k]!=' ') str+=s[k++];
            k++;  
            x=mymap[str];
            if (!x)
            { 
               mymap[str]=++p;
               x=p;
            } 
            a[x]=0;
            while (s[k]>='0' && s[k]<='9' ) a[x]=a[x]*10+s[k++]-'0'; 
            k++;
            Num=0;
            while (k<l)
            {
                str="";   Num++;
                while (s[k]!=' ' && s[k]!='\n' && k<l)  str+=s[k++];
                g=mymap[str]; 
                if (!g)
                {
                  mymap[str]=++p;
                  g=p;
                } 
                father[g]=x;
                k++;   
            } 
            son[x]=Num;
        }     
        son[0]=0;
        for (i=1;i<=n;i++)
         if (!father[i]) son[0]++; 
}
int GetAnswer()
{
    int dp[205][205],i,j,k,h,f;
    memset(dp,-1,sizeof(dp));  
    for (i=0;i<=n;i++) dp[i][0]=0; 
    while (!myqueue.empty()) myqueue.pop();
    for (i=1;i<=n;i++) 
    {
       if (!son[i])  myqueue.push(i); 
       totol[i]=1;
    }
    totol[0]=0;
    while (1)
    {
          h=myqueue.front();  myqueue.pop();    
          if (!h) break;     
          dp[h][totol[h]]=a[h];          
          son[father[h]]--;
          if (!son[father[h]]) myqueue.push(father[h]);
          f=father[h];
          totol[f]+=totol[h];
          for (i=0;i<=n;i++) temp[i]=dp[f][i];
          for (k=1;k<=totol[h];k++)
            for (i=totol[f]-k;i>=0;i--)
              if (dp[f][i]>=0)
              {
                  if (temp[i+k]<0 || temp[i+k]>dp[f][i]+dp[h][k]) 
                  temp[i+k]=dp[f][i]+dp[h][k];                                
              }      
          for (i=0;i<=n;i++) dp[f][i]=temp[i];            
    }
    int ans=2000000000;
    for (k=0;k<=n;k++)
     for (i=m;i<=n;i++)
      if (dp[k][i]>=0)  ans=ans<dp[k][i]?ans:dp[k][i];
    return ans; 
}
int main()
{ 
    while (gets(s))
    {
        if (s[0]=='#') break;  
        input();
        printf("%d\n",GetAnswer()); 
    }
    return 0;   
}