BZOJ 1065 奥运物流

http://www.lydsy.com/JudgeOnline/problem.php?id=1065

思路:由于n个点，有n条边，因此由根就会引出一个环，我们枚举环的长度，在那个长度断开，我们假设len为环的长度。

由于R(i)满足

而产生环时，R[1]=Σci*k^di + R[1]*(k^len),得到

R[1]=(Σci*k^di)/(1-k^len)

因此我们枚举len，然后做树形DP，f[i][j][k]代表第i个点，修改了j次，当前深度为k

那么最后的贡献是Σf[i][j][1]，i为1的直接儿子，用一个01背包统计，最后答案就是(ans+c[1])/(1-k^len)

有个蛋疼的地方就是做01背包的时候。。要注意循环变量的顺序，不要重复统计。。

#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
int n,m,pre[200005];
double K[200005],c[200005],f[80][80][80],g[80][80][80],F[200005];
int read(){
    int t=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
    return t*f;
}
void dp(int x,int dep){
    for (int i=2;i<=n;i++) if (pre[i]==x) dp(i,dep+1);
    for (int d=std::min(2,dep);d<=dep;d++){
         for (int j=0;j<=m;j++) F[j]=0;
         for (int i=2;i<=n;i++)
              if (pre[i]==x)
              for (int j=m;j>=0;j--)
                for (int k=j;k>=0;k--)
                    F[j]=std::max(F[j],F[k]+g[i][j-k][d]);
        for (int i=0;i<=m;i++)
            f[x][i][d]=F[i]+c[x]*K[d];        
    }    
    if (dep>1){
        for (int i=0;i<=m;i++) F[i]=0;
        for (int i=2;i<=n;i++)
            if (pre[i]==x)
            for (int j=m;j>=0;j--)
                for (int k=j;k>=0;k--)
                    F[j]=std::max(F[j],F[k]+g[i][j-k][1]);
        for (int i=1;i<=m;i++)
            f[x][i][1]=F[i-1]+c[x]*K[1];    
    }
    for (int j=0;j<=m;j++)
         for (int d=0;d<dep;d++)
            g[x][j][d]=std::max(f[x][j][d+1],f[x][j][1]);
}
int main(){
    n=read();m=read();scanf("%lf",&K[1]);
    for (int i=2;i<=n;i++) K[i]=K[i-1]*K[1];
    for (int i=1;i<=n;i++) pre[i]=read();
    for (int i=1;i<=n;i++) scanf("%lf",&c[i]);
    double ans=0;
    for (int I=pre[1],len=2;I-1;I=pre[I],len++){
        for (int i=1;i<=n;i++)
         for (int j=0;j<=m;j++)
           for (int k=0;k<=n;k++)
               f[i][j][k]=g[i][j][k]=0;
        int tmp=pre[I];pre[I]=1;   
        for (int i=2;i<=n;i++) if (pre[i]==1) dp(i,1);
        for (int i=0;i<=m;i++) F[i]=0;
        for (int i=2;i<=n;i++)
         if  (pre[i]==1)
            for (int j=m;j>=0;j--)
                 for (int k=j;k>=0;k--)
                   F[j]=std::max(F[j],F[k]+f[i][j-k][1]);
        double now=0;
        for (int i=0;i<m;i++) now=std::max(now,F[i]);    
        if (tmp==1) now=std::max(now,F[m]);
        pre[I]=tmp;
        ans=std::max(ans,(now+c[1])/(1-K[len]));    
    }
    printf("%.2lf
",ans);
}