【bzoj1065】[NOI2008]奥运物流

2015.06.24 14:38 Wed | 35次阅读 | 旧日oi | 固定链接 | 源码

Description

题解

先考虑不带环的情况。
每个点对答案的贡献为c[i]*dep[i],dep[i]为i的深度。显然每次修改都要把一个节点的父亲设为1。
很容易想到,令f[i][j]表示以i为根的子树中修改j次能获得的最大价值。那么我们如何转移呢?
f[i][j]=max(f[v1][k1]+f[v2][k2]+……)+c[i]*dep[i]?(k1+k2+...=j)
这样看起来好像挺对的哈,但是如果修改i的父亲为1呢?
f[i][j]=max(f[v1][k1]+f[v2][k2]+……)/(k^(dep[i]-1}+c[i]*k?(k1+k2+...=j-1)
这个显然不对了吧,因为如果i的子节点中有的的父亲被修改为1,那么在这里就挂掉了……
那我们令f[i][j][k]表示以i为根的子树中修改j次,修改的状态为k(二进制)?这显然mle……或者ce……
于是这个办法就行不通了。
考虑这个办法为什么不行,因为儿子节点的选择会影响到父亲节点的选择。
于是我们应该怎么办呢。让儿子“预知”一下未来!
令f[i][j][d]表示以i为根的子树中修改j次,且i的深度为d时的最大稳定度。
这样比较好转移,令g[i][j][d]=max(f[i][j][d+1],f[i][j][1]),意义是如果父亲节点深度是d,那么不修改这个节点的话,这个点的深度就是d+1,修改的话就是1,取一下最大值。
然后转移方程:f[i][j][d]=max(g[v1][k][d]+g[v2][k2][d])……,k1+k2+...=j) 这里的d也是要枚举的。
如果修改i,那么有f[i][j][1]=max(g[v1][k][1]+g[v2][k2][1])……,k1+k2+...=j-1)。
这样核心的部分我们就搞完了,实现上还有一些细节,比如根节点的深度是0啊,与根节点相邻的点的深度肯定是1啦等等,这都是细节,看代码就行了。
用这种思想可以解决noi2006的网络收费,ioi2005的riv。
接下来考虑环。我们先找出来环
for(int i=fa[1];i!=1;i=fa[i]) cir[++cnt]=i;
如果整张图就是一个环,设环的长度是len,那么经过推导我们可以得出R1=∑(c[i]*dep[i])/(1-k^len)。而环上带一些树的话也是这个公式。所以我们枚举环的长度,假设环的长度为3,那么我们就把i,fa[i],fa[fa[i]],固定下来不再修改,让fa[fa[fa[i]]]=1(如果这个点的fa不是1,则m要减1),然后其他的就形成了一颗树,这时环上的点的深度都是固定的,把这些点都标记上。我们把i=2到n的(fa[i],i)作为边加入。然后进行上述的dp过程。注意一个点的儿子如果是环上节点,那么不要用这个点更新信息。
做完之后,我们再在环上做一遍dp,ans[k]表示修改k次的最大稳定值,则ans[k]=max(dp[cir[1]][k1][dep[cir[1]]]+dp[cir[2]][k2][dep[cir[2]]]+...)k1+k2+...=k.
那么用这个环做出来的答案就是ans[m]/(1-k^(len));这样就搞完了。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define inf 0x4f4f4f4f
using namespace std;
#define N 65
int n,m,cnt;
double K,c[N],power[N]={1};
int fa[N],cir[N],dep[N];
bool vis[N];
double f[N][N][N],g[N][N][N];
struct edge
{
    int to,next;
}e[N];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
void DP(int u,int d)
{
    for(int i=h[u];e[i].to;i=e[i].next)
    DP(e[i].to,d+1);
    if(!vis[u]&&d!=1)
    {
        for(int v,i=h[u];e[i].to;i=e[i].next)
        {
            v=e[i].to;if(vis[v]) continue;
            for(int j=m-1;j>=0;j--)
            for(int k=0;k<=j;k++)
                f[u][j+1][1]=max(f[u][j+1][1],f[u][j-k+1][1]+g[v][k][1]);
        }
        for(int j=1;j<=m;j++)
        {
            f[u][j][1]+=power[1]*c[u];
            g[u][j][0]=f[u][j][1];
        }
    }
    for(int de=vis[u]?dep[u]:(1+(d!=1));de<=d;de++)
    {
        for(int v,i=h[u];e[i].to;i=e[i].next)
        {
            v=e[i].to;if(vis[v]) continue;
            for(int j=m;j>=0;j--)
            for(int k=0;k<=j;k++)
                f[u][j][de]=max(f[u][j][de],f[u][j-k][de]+g[v][k][de]);
        }
        for(int j=0;j<=m;j++)
        {
            f[u][j][de]+=power[de]*c[u];
            if(de) g[u][j][de-1]=max(f[u][j][de],f[u][j][1]);
        }
    }
}
double ans[N];
int main()
{
    cin>>n>>m>>K;
    for(int i=1;i<=n;i++) scanf("%d",&fa[i]);
    for(int i=1;i<=n;i++) scanf("%lf",&c[i]);
    for(int i=1;i<=n;i++) power[i]=power[i-1]*K;
    for(int i=fa[1];i!=1;i=fa[i]) cir[++cnt]=i;
    cir[0]=vis[1]=1;
    double ret=0;
    for(int i=1;i<=cnt;i++)
    {
        if(i!=cnt) m--;
        for(int j=1;j<=i;j++) dep[cir[j]]++;
        vis[cir[i]]=1;
        int tmp=fa[cir[i]];fa[cir[i]]=1;
        memset(h,0,sizeof(h));tp=0;
        for(int j=2;j<=n;j++) ae(fa[j],j);
        fa[cir[i]]=tmp;
        memset(ans,0,sizeof(ans));
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        DP(1,0);
        for(int j=0;j<=i;j++)
        {
            for(int k=m;k>=0;k--)
            {
                double tmp=0;
                for(int p=0;p<=k;p++)
                tmp=max(tmp,ans[p]+f[cir[j]][k-p][dep[cir[j]]]);
                ans[k]=tmp;
            }
        }
        ret=max(ans[m]/(1-power[i+1]),ret);
        if(i!=cnt) m++;
    }
    printf("%.2lf",ret);
}```