题解 P4918 【信仰收集】

· · 题解

首先应该不难想到一维dp,dp[i]表示到第i个点的最大受益,对每个点dfs到它所有后面距离它a,b长度的点并更新

然而后来这样复杂度最坏是O(n^b),比如下面这种图:

如果b=2那么对于左侧的每一个点,都会去更新右边的所有点,复杂度就是平方级别的,你可以试想如果这种结构重复十次然后b=20的复杂度

gg

其实做到这里60分也是不错的成绩了,正解是不太好想的二维dp,意会一下就好

那么,先拓扑排序,对于一个点$u$,我们枚举它直接相连的点$v$,那么转移有四种: $$dp[v][i]=max(dp[v][i],dp[u][i+1])(0<i<b)$$ $$dp[v][a-1]=max(dp[v][a-1],dp[u][0]-w_a)$$ $$dp[v][b-1]=max(dp[v][b-1],dp[u][0]-w_b)$$ $$dp[v][0]=max(dp[v][0],dp[u][1]+w[v])$$($w[i]$表示$i$处收益) 然后就可以愉快的水过了(雾),注意$dp[1][0]$的初值 难度主要集中在思维难度上 $ACcode 
    struct edge
    {
        int to,next;
    }e[maxn<<4];
    int head[maxn],cnt=0;
    int f[maxn][51];
    int rudu[maxn];
    int w[maxn];
    inline void addedge(int u,int v)
    {
        e[++cnt].to=v,e[cnt].next=head[u],head[u]=cnt;
    }
    queue<int>q;
    void del(int x)
    {
        for(int i=head[x];i;i=e[i].next)
        {
            int v=e[i].to;
            rudu[v]--;
            if(!rudu[v]&&v!=1)q.push(v);
        }
    }
    int main()
    {
        scanf("%d%d%d%d%d%d%d",&n,&m,&k,&a,&b,&wa,&wb);
        int u,v;
        for(int i=1;i<=n;++i)u=read(),v=read(),w[u]+=v;
        for(int i=1;i<=k;++i)u=read(),v=read(),addedge(u,v),rudu[v]++;
        memset(f,-127,sizeof(f));
        for(int i=2;i<=m;++i)
            if(!rudu[i])q.push(i);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            del(u);
        }
        q.push(1);
        f[1][0]=w[1];
        while(!q.empty())
        {
            int x=q.front();q.pop();
            del(x);
            for(int i=head[x];i;i=e[i].next)
            {
                int v=e[i].to;
                if(f[x][0]!=f[0][0])
                {
                    if(a!=1)f[v][a-1]=max(f[v][a-1],f[x][0]-wa);
                    else f[v][0]=max(f[v][0],f[x][0]-wa+w[v]);
                }
                if(f[x][0]!=f[0][0])
                {
                    if(b!=1)f[v][b-1]=max(f[v][b-1],f[x][0]-wb);
                    else f[v][0]=max(f[v][0],f[x][0]-wb+w[v]);
                }
                if(f[x][1]!=f[0][0])f[v][0]=max(f[v][0],f[x][1]+w[v]);
                for(int j=b;j>1;--j)
                    if(f[x][j]!=f[0][0])f[v][j-1]=max(f[v][j-1],f[x][j]);
            }
        }
        int ans=0;
        for(int i=1;i<=m;++i)ans=max(ans,f[i][0]);
        printf("%d\n",ans);
    }