需要掌握的东西:
动态规划-》树形DP
动态规划-》转移将来状态
那么,这里有一篇论文(2009 WinterCamp)
先确定以下几点共识:
1、如果根(1号节点)没有后继,那么这个图就是一棵树
2、树的深度越小越好
对于第一条,显然没有问题,那么对于第二条呢?
将题目中的式子不断代入,我们可以得到\(R_1\)的表达式
\[R_1=\frac{\sum_{i=1}^{n}C_i\times k^{d_{i,1}}}{1-k^{len}}\]其中,len表示图中唯一的环的长度,\(d_{i,1}\)表示点\(i\)到1号点的距离
那么,题目就变成这样了:
将编号为2~n的点中选取\(m\)个点,修改其后继节点为1,使上式值最大,求这个最大值
显然,这是01背包,但是,若将某个点的父节点设为1,那么其子节点门也会受到影响
所以要计算这一步操作的贡献,也就是预估未来状态
状态的表示和状态的转移都在论文里了,这里不再说什么了……我得洗洗睡了,毕竟现在不早了
下面是AC-Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=65,MAXM=65;
const double INF=1e10;
int Fa[MAXN];
int N,M;
int son[MAXN];
int Graph[MAXN][MAXN];
double Pow[MAXN];
double K;
double f[MAXN][MAXM][MAXN],g[MAXN][MAXM],Ci[MAXN];
double ans=-INF,nowans=0;
int nowdo=-1,ringlen=-1;
void dfs(int u,int fa,int deep)
{
int v,num=0;
for (int v=1;v<=N;v++)
if (Graph[u][v]&&v!=fa)
dfs(v,u,deep+1);
for (int v=1;v<=N;v++)
if (Graph[u][v]&&v!=fa)
son[++num]=v;
for (int j=0;j<=deep;j++)
{
for (int i=1;i<=num;i++)
for (int k=0;k<=M;k++)
g[i][k]=-INF;
g[0][0]=0;
for (int i=1;i<=num;i++)
{
v=son[i];
for (int k=0;k<=M;k++)
{
for (int l=0;l+k<=M;l++)
{
g[i][l+k]=max(g[i][l+k],g[i-1][l]+f[v][k][j+1]);
if (l+k+(u!=1)<=M)
g[i][l+k+(u!=1)]=max(g[i][l+k+(u!=1)],g[i-1][l]+f[v][k][1]);
}
}
}
double wme=Pow[j]*Ci[u];
for (int k=0;k<=M;k++)
f[u][k][j]=max(g[num][k]+wme,k?f[u][k-1][j]:-INF);
}
}
int main()
{
scanf("%d%d%lf",&N,&M,&K);
Pow[0]=1;
for (int i=1;i<=N;i++)
Pow[i]=Pow[i-1]*K;
for (int i=1;i<=N;i++)
scanf("%d",&Fa[i]);
for (int i=1;i<=N;i++)
scanf("%lf",&Ci[i]);
nowdo=Fa[1];ringlen=1;
while (nowdo!=1)
{
ringlen++;
memset(Graph,0,sizeof(Graph));
for (int i=2;i<=N;i++)
if (i!=nowdo)
Graph[i][Fa[i]]=Graph[Fa[i]][i]=1;
else
Graph[i][1]=Graph[1][i]=1;
dfs(1,0,0);
if (M||Fa[nowdo]==1)
{
if (Fa[nowdo]!=1)
nowans=f[1][M-1][0];
else
nowans=f[1][M][0];
//cerr<<nowans<<" "<<1-Pow[ringlen];
ans=max(nowans/(1-Pow[ringlen]),ans);
}
nowdo=Fa[nowdo];
}
printf("%.2lf\n",ans);
return 0;
}