bzoj2427 [HAOI2010]软件安装——缩点+树形DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2427

今天的考试题...好不容易一次写对了树形DP，却没发现有环的情况...

发现自己 tarjan 都不太熟了，差点没写上那个 vis 数组！

还有点要注意的地方，如果一个环跟外部都不连边，要专门把它连到0点上去；

然后就是普通的树形DP了。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,w[],v[],head[],ct,f[][],siz[],ans,cr,col[],hd[],cnt;

int dfn[],low[],tim,sta[],top,vv[],ww[];

bool vis[],in[];

struct N{

    int to,next;

    N(int t=,int n=):to(t),next(n) {}

}edge[],ed[];

void dp(int x)

{

    siz[x]=ww[x]; f[x][ww[x]]=vv[x]; f[x][]=;

//    cout<<x<<endl;

//    printf("%d head=%d\n",x,head[x]);

    for(int j=hd[x],u;j;j=ed[j].next)

    {

        dp(u=ed[j].to);

        siz[x]+=siz[u];

        for(int i=min(m,siz[x]);i>=ww[x];i--)

            for(int k=min(i-ww[x],siz[u]);k>=;k--)

//            {

                f[x][i]=max(f[x][i],f[u][k]+f[x][i-k]);

//                if(f[x][i]>=0)printf("u=%d i=%d k=%d f[%d][%d]=%d\n",u,i,k,x,i,f[x][i]);

//            }

    }

//    printf("return:%d\n",x);

}

void tarjan(int x)

{

    dfn[x]=low[x]=++tim;

    sta[++top]=x; vis[x]=;//

    for(int i=head[x];i;i=edge[i].next)

    {

        int u=edge[i].to;

        if(!dfn[u])

        {

            tarjan(u);low[x]=min(low[x],low[u]);

        }

        else if(vis[u])//

            low[x]=min(low[x],dfn[u]);

    }

    if(low[x]==dfn[x])

    {

        cr++;

        while(sta[top]!=x)

        {

            col[sta[top]]=cr;

            ww[cr]+=w[sta[top]];

            vv[cr]+=v[sta[top]];

            vis[sta[top]]=; top--;

        }

        ww[cr]+=w[x]; vv[cr]+=v[x];

        col[x]=cr; vis[x]=; top--;

    }

}

int main()

{

//    freopen("software.in","r",stdin);

//    freopen("software.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&w[i]);

    for(int i=;i<=n;i++)scanf("%d",&v[i]);

    for(int i=,x;i<=n;i++)

    {

        scanf("%d",&x);

        edge[++ct]=N(i,head[x]); head[x]=ct;

    }

    for(int i=;i<=n;i++)

        if(!dfn[i])tarjan(i);

    for(int i=;i<=n;i++)//

        for(int j=head[i];j;j=edge[j].next)

        {

            int u=edge[j].to;

            if(col[i]==col[u])continue;//

            ed[++cnt]=N(col[u],hd[col[i]]); hd[col[i]]=cnt;

            in[col[u]]=;

        }

    memset(f,-,sizeof f);

    for(int i=;i<=cr;i++)

        if(in[i]==){ed[++cnt]=N(i,hd[]); hd[]=cnt;}//注意这部分！

    dp();

    for(int i=;i<=m;i++)ans=max(ans,f[][i]);

    printf("%d",ans);

    return ;

}