记录编号	255268	评测结果	AAAAAAAAAA
题目名称	[CTSC 1997]选课	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.259 s
提交时间	2016-04-27 11:32:34	内存使用	3.06 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=600;
int route[maxn];int top=0;
int p[maxn];
int f[maxn][maxn];
bool root[maxn][maxn];int left[maxn][maxn];
struct edge{
	int to,next;
}lst[maxn];int len=1;
int first[maxn];
void addedge(int a,int b){
	lst[len].to=b;
	lst[len].next=first[a];
	first[a]=len++;	
}
struct node{
	int lch,rch;
}t[maxn];
void convert(int rt){
	if(!first[rt])return;
	int pt=first[rt];
	t[rt].lch=lst[pt].to;
	for(;pt;pt=lst[pt].next){
		t[lst[pt].to].rch=lst[lst[pt].next].to;
	}
	for(pt=first[rt];pt;pt=lst[pt].next)convert(lst[pt].to);
}
int max(int a,int b){
	return a>b?a:b;
}
int F(int rt,int cnt){
	if(!rt||!cnt)return 0;
	if(f[rt][cnt])return f[rt][cnt];
	f[rt][cnt]=F(t[rt].rch,cnt);
	root[rt][cnt]=false;
	int tmp;
	for(int k=0;k<cnt;++k){
		tmp=F(t[rt].lch,k)+F(t[rt].rch,cnt-k-1)+p[rt];
		if(tmp>f[rt][cnt]){
			f[rt][cnt]=tmp;
			root[rt][cnt]=true;
			left[rt][cnt]=k;
		}
	}
	return f[rt][cnt];
}
void output(int rt,int cnt){
	if(!rt||!cnt)return;
	if(!root[rt][cnt])output(t[rt].rch,cnt);
	else{
		route[top++]=rt;
		output(t[rt].lch,left[rt][cnt]);
		output(t[rt].rch,cnt-left[rt][cnt]-1);
	}
}
int main(){
	freopen("course.in","r",stdin);
	freopen("course.out","w",stdout);
	int m,n;scanf("%d %d",&m,&n);
	int tmp;
	for(int i=1;i<=m;++i){
		scanf("%d %d",&tmp,p+i);
		addedge(tmp,i);
	}
	convert(0);
	printf("%d\n",F(t[0].lch,n));
	output(t[0].lch,n);
	sort(route,route+top);
	for(int i=0;i<top;++i)printf("%d\n",route[i]);
	fclose(stdin);fclose(stdout);
	return 0;
}