记录编号	162747	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2015-05-19 17:59:28	内存使用	6.03 MiB

#include <cstdio>

using namespace std;

int group[100][5000][2],total_money,n,son[80][50],important[80],price[80],q,group_cs,f[500000],process_array[50],temp;//0 is price,1 is value
bool have_father[61];

void PLZH(int,int);
void ADD_GROUP(int);

inline int in(){
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')c=getchar();
	for(;c>='0'&&c<='9';c=getchar())x=x*10+c-48;
	return x;
}

int main()
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	total_money=in();n=in();temp=in();
	total_money/=10;
    for(int i=1;i<=n;i++){
		price[i]=in();important[i]=in();q=in();
        important[i]*=price[i];price[i]/=10;
        if(q>0){
            son[q][++son[q][0]]=i;
            have_father[i]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(have_father[i]){
            continue;
        }
        else{
            group_cs++;
            if(son[i][0]==0){
                group[group_cs][0][0]=1;
                group[group_cs][1][0]=price[i];
                group[group_cs][1][1]=important[i];
            }
            else{
                temp=i;
                group[group_cs][0][0]=1;
                group[group_cs][1][0]=price[i];
                group[group_cs][1][1]=important[i];
                PLZH(1,1);
            }
        }
    }
    for(int i=1;i<=group_cs;i++){
        for(int j=total_money;j>=0;j--){
            for(int k=1;k<=group[i][0][0];k++){
                if(j<group[i][k][0]) continue;
                if(f[j]<f[j-group[i][k][0]]+group[i][k][1]){
                    f[j]=f[j-group[i][k][0]]+group[i][k][1];
                }
            }
        }
    }
    printf("%d",f[total_money]);
    return 0;
}

void PLZH(int starter,int cs_now)
{
    for(int i=starter;i<=son[temp][0];i++){
		if(price[son[temp][i]]>total_money) continue;
        process_array[cs_now]=son[temp][i];
        ADD_GROUP(cs_now);
        PLZH(i+1,cs_now+1);
    }
    return;
}

void ADD_GROUP(int gs)
{
    group[group_cs][0][0]++;
    int pc_=group[group_cs][0][0];
    group[group_cs][pc_][0]=price[temp];
    group[group_cs][pc_][1]=important[temp];
    for(int i=1;i<=gs;i++){
        group[group_cs][pc_][0]+=price[process_array[i]];
        group[group_cs][pc_][1]+=important[process_array[i]];
        if(group[group_cs][pc_][0]>total_money){
			group[group_cs][0][0]--;return;
        }
    }
    return;
}