NOI2008奥运物流

Posted on By 二价氢

需要掌握的东西:

动态规划-》树形DP

动态规划-》转移将来状态

那么,这里有一篇论文(2009 WinterCamp)

徐源盛-对一类动态规划问题的研究.ppt

徐源盛-对一类动态规划问题的研究.pdf

先确定以下几点共识:

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;
}