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;
}
分类: 所有

1 条评论

luobobo · 2017年5月20日 12:50 下午

%%%%%%abs判环算法就此诞生%%%%%%%

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *