记录编号	45058	评测结果	AAAAAAAAAA
题目名称	[郑州101中学] 圣战	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	1.061 s
提交时间	2012-10-22 09:21:32	内存使用	54.82 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
	int nex,s;
}a[20005];
struct edge{
	int nex;
	int y;
}e[30000];
int N,M;
int x,y,o,p,i;
int v[20001];
int w[20001];
int f[20005][600];
bool t[20005][600];
void add(int x,int y){
	a[x].s++;
	p++;
	e[p].y=y;
	e[p].nex=a[x].nex;
	a[x].nex=p;
	if (a[x].s==3){
		o++;
		a[o].s=2;
		a[o].nex=e[a[x].nex].nex;
		p++;
		e[p].y=o;
		e[a[x].nex].nex=p;
		a[x].s=2;
	}
}
int cul(int i,int u){
	if (u==0) return 0;
	int tmp=a[i].nex;
	int x1x=e[tmp].y;
	tmp=e[tmp].nex;
	int x2x=e[tmp].y;
	int maxn=0;
	if (x1x==0 && x2x==0 && u>0)
		return w[i];
	if (x2x==0 && u>0){
		if (!t[x1x][u-v[i]]){
			t[x1x][u-v[i]]=true;
			f[x1x][u-v[i]]=cul(x1x,u-v[i]);
		}
		return f[x1x][u-v[i]]+w[i];
	}
	for (int x=0;x<=u;x++)
		if (u-x-v[i]>=0){
		if (!t[x1x][x]){
			f[x1x][x]=cul(x1x,x);
			t[x1x][x]=true;
		}
		if (!t[x2x][u-x-v[i]]){
			f[x2x][u-x-v[i]]=cul(x2x,u-x-v[i]);
			t[x2x][u-x-v[i]]=true;
		}
		tmp=f[x1x][x]+f[x2x][u-x-v[i]]+w[i];
		if (tmp>maxn) maxn=tmp;
	}
	return maxn;
}
int main(){
	freopen("charge.in","r",stdin);
	freopen("charge.out","w",stdout);
	scanf("%d%d",&M,&N);
	p=0;
	o=M;
	memset(t,false,sizeof(t));
	memset(v,0,sizeof(v));
	memset(w,0,sizeof(w));
	for (i=0;i<=M;i++)
		v[i]=1;
	for (i=1;i<=M;i++){
		scanf("%d%d",&x,&w[i]);
		add(x,i);
	}
	f[0][N]=cul(0,N);
	printf("%d",f[0][N]+40000000);
	return 0;
}