记录编号	184588	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]奥运物流	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.668 s
提交时间	2015-09-03 17:10:25	内存使用	3.40 MiB

#include<cstdio>
#include<deque>
#include<cstring>
#include<iostream>
using namespace std;
double f[61][61][61]={0},g[61][61][61]={0};
int N,m,father[80];
double powk[80]={0};
double k,C[65];
deque<int> s[70];
void DP(int now,int x,int dep)//now是当前将哪个点从环上切断了，dep是当前节点的深度
{
	for(int i=0;i<s[x].size();i++) if(s[x][i]!=now&&s[x][i]!=1) DP(now,s[x][i],dep+1);
	for(int i=1;i<=dep;i++)//枚举x到1的距离
	{
		int tem=0;
		if(dep>1&&i==1)//对x进行了修改
			tem=1;
		double F[70]={0};
		for(int q=0;q<s[x].size();q++)
		{
			int v=s[x][q];
			if(v==1||v==now) continue;
			for(int j=m;j>=0;j--)
				for(int p=j;p>=0;p--)//分组背包
				{
					F[j]=max(F[j],F[p]+g[v][j-p][i]);
				}
	    }
		for(int j=tem;j<=m;j++) f[x][j][i]=F[j-tem]+C[x]*powk[i];
	}
	for(int i=0;i<=m;i++)
		for(int d=0;d<dep;d++) g[x][i][d]=max(f[x][i][d+1],f[x][i][1]);
}
void work()
{
	int len=2;//环的长度
	double ans=0;
	for(int i=father[1];i!=1;i=father[i],len++)//枚举将环上的哪个点连到1上
	{
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		for(int j=2;j<=N;j++) if(father[j]==1||j==i) DP(i,j,1);//对1的子树进行DP
		double F[70]={0};
		for(int x=2;x<=N;x++)//对1的子树进行泛化背包
		{
			if(!(father[x]==1||x==i)) continue;
			for(int j=m;j>=0;j--)
				for(int k=j;k>=0;k--)
				{
					F[j]=max(F[j],F[k]+f[x][j-k][1]);
				}
		}
		int tem;
		if(father[i]==1) tem=m;//当i的后继是1是，不用修改后继
		else tem=m-1;
		for(int j=0;j<=tem;j++) ans=max(ans,(F[j]+C[1])/(1-powk[len]));
	}
	printf("%.2lf",ans);
}
int main()
{
	freopen("trans.in","r",stdin);
	freopen("trans.out","w",stdout);
	scanf("%d%d%lf",&N,&m,&k);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&father[i]);
		s[father[i]].push_back(i);
	}
	for(int i=1;i<=N;i++) scanf("%lf",&C[i]);
	powk[0]=1;
	for(int i=1;i<=N;i++) powk[i]=powk[i-1]*k;
	work();
	return 0;
}