Tarjan水题系列(4):HAOI2010 软件安装

题目：

现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。

(0≤N≤100,0≤M≤500,0≤Wi≤M,0≤Vi≤1000)

大意:

有向图选一个节点同时需要选它的前驱，求满足容量关系的最大点权和

思路:

首先依赖关系可以成环故选了其中一个相当于选了所有故可以缩点处理

缩完点后由于一个点只有一个前驱故剩下的图构成森林将其与0号点相连构成一个树此时本题就成了树上背包的裸题题干疯狂暗示注意选了父亲才能选儿子故此时状态dp[u][w]是选了u节点后该子树在w容量时取得的最优解又由于选了u节点故dp[u][w]需要初始化由状态定义知最终答案在dp[0][M]取得

下面是代码

 #include <cstdio>

 #include <iostream>

 #define r(x) x=read()

 #define MAXX 1005

 using namespace std;

 int f[MAXX][MAXX],w2[MAXX],z2[MAXX],w[MAXX],z[MAXX],sta[MAXX],id[MAXX],

     low[MAXX],dfn[MAXX],h[][MAXX],cnt[],fa[MAXX],k,num,top,n,m,ans,to;

 struct edge{int to,nex;}e[][];

 void add(int u,int to,int d)

 {

   cnt[d]++;

   e[d][cnt[d]]=(edge){to,h[d][u]};

   h[d][u]=cnt[d];

 }

 void tarjan(int u)

 {

   low[u]=dfn[u]=++k;sta[++top]=u;

   for(int i=h[][u];i;i=e[][i].nex)

   {

     int to=e[][i].to;

     if(!dfn[to])

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

     else

       if(!id[to])

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

   }

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

   {

     id[u]=++num;

     while(sta[top]!=u)

     {

       id[sta[top]]=num;

       --top;

     }

     --top;

   }

 }

 void dfs(int u)

 {

   for(int i=w[u];i<=m;++i) f[u][i]=z[u];

   for(int p=h[][u];p;p=e[][p].nex)

   {

     dfs(e[][p].to);

     for(int i=m;i>=w[u];--i)

       for(int j=;j<=i-w[u];++j)

           f[u][i]=max(f[u][i],f[u][i-j]+f[e[][p].to][j]);

   }

 }

 int read()

 {

   char ch=;int w=;

   while(ch<''||ch>''){ch=getchar();}

   while(ch>=''&&ch<=''){w=w*+ch-'';ch=getchar();}

   return w;

 }

 int main()

 {

   r(n),r(m);

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

     r(w2[i]);

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

     r(z2[i]);

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

   {

     r(to);

     if(to)

       add(to,i,);

   }

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

     if(!id[i])

       tarjan(i);

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

   {

       w[id[i]]+=w2[i];

       z[id[i]]+=z2[i];

     for(int j=h[][i];j;j=e[][j].nex)

     {

       if(id[e[][j].to]!=id[i])

         add(id[i],id[e[][j].to],),++fa[id[e[][j].to]];

     }

   }

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

     if(!fa[i]) add(,i,);

   dfs();

   printf("%d",f[][m]);

   return ;

 }

巴特西

Tarjan水题系列(4):HAOI2010 软件安装

最新文章

热门文章