HAOI2010

题意：给定一些软件，每个软件占 Wi 空间，价值 Vi，依赖第 Di 个软件。求在 M 空间的电脑最多可以装多少价值的软件。软件 i 可以安装当且仅当软件 Di 已安装，默认 Di=0 意思是没有依赖，可以随意安装。

思路，由于图中相当于有 n 个节点，n 条边，所以必定有自环。我们可以用 Tarjan 判环缩点 (当然我用的不是，我不会打)，再进行树上背包。

问题一：缩点。%%%HZWER%%% 用的是 Tarjan（行数稍稍多了点）, 貌似很高级，但是我不会打 Tarjan，于是我经过思考，想到了一个根据这幅图特性得出的专用判环函数（貌似思想和 Tarjan 一样, 只是行数少）

判环缩点函数：

int color[MX],cnum,vis[MX];
int sch(int x,int col)
{
    if((x==0||)(vis[x]==0&&color[x]))return 0;
    if(vis[x])return color[x];
    vis[x]=1,color[x]=col,cnum++;
    int nowc=sch(da[x],col+1);
    if(nowc==0)return 0;
    else if(nowc<=col){color[x]=nowc;return nowc;}
    return nowc;
}

再 main 函数中：

for(int i=1; i<=n; i++)if(!color[i])memset(vis,0,sizeof(vis)),sch(i,++cnum);

十二行搞定判环缩点。此时就可以把每一种颜色 (color 数组) 当成一个点，建树，建树的同时弄树上背包。对于每个子节点当成一个分组，进行分组背包问题，物品的大小就是分配的空间。由于子节点可以选的前提是父节点已选，所以有这么一句：

for(int j=m;j>=0;j--)
{
    if(j>=wei[x])f[x][j]=f[x][j-wei[x]]+val[x];
    else f[x][j]=0;
}

这个代码差不多可以称全网较短了。

#include <iostream>
#include <cstdio>
#include <cstring>
#define MX 1001

using namespace std;

int yl[MX],app[MX],va[MX],wa[MX],da[MX],mp[MX][MX],chud[MX];
int val[MX],wei[MX];
int n,m;
int fst[MX],nxt[MX],lnum=-1,u[MX],v[MX],f[MX][MX];

void addeg(int nu,int nv)
{
    u[++lnum]=nu,v[lnum]=nv,nxt[lnum]=fst[nu],fst[nu]=lnum;
}

void input()
{
    memset(fst,0xff,sizeof(fst));
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)scanf("%d",&wa[i]);
    for(int i=1; i<=n; i++)scanf("%d",&va[i]);
    for(int i=1; i<=n; i++)scanf("%d",&da[i]);
}

int color[MX],cnum,vis[MX];
int sch(int x,int col)
{
    if(x==0)return 0;
    if(vis[x]==0&&color[x])return 0;
    if(vis[x])return color[x];
    vis[x]=1,color[x]=col,cnum++;
    int nowc=sch(da[x],col+1);
    if(nowc==0)return 0;
    else if(nowc<=col){color[x]=nowc;return nowc;}
    return nowc;
}

void dfs(int x)
{
    for(int i=fst[x]; i!=-1; i=nxt[i])
    {
        dfs(v[i]);
        for(int j=m-wei[x]; j>=0; j--)
            for(int k=0;k<=j;k++)
                f[x][j]=max(f[x][j],f[x][k]+f[v[i]][j-k]);
    }
    for(int j=m;j>=0;j--)
    {
        if(j>=wei[x])f[x][j]=f[x][j-wei[x]]+val[x];
        else f[x][j]=0;
    }
}

int main()
{
    freopen("install.in","r",stdin),freopen("wa.out","w",stdout);
    input();
    for(int i=1; i<=n; i++)if(!color[i])memset(vis,0,sizeof(vis)),sch(i,++cnum);
    for(int i=1; i<=n; i++)if((!mp[color[da[i]]][color[i]])&&(color[da[i]]!=color[i]))addeg(color[da[i]],color[i]),mp[color[da[i]]][color[i]]=1,chud[color[i]]++;
    for(int i=1; i<=n; i++)if(chud[color[i]]==0)addeg(0,color[i]),chud[color[i]]++;
    for(int i=1; i<=n; i++)val[color[i]]+=va[i],wei[color[i]]+=wa[i];
    dfs(0);
    cout<<f[0][m]<<endl;
    return 0;
}