[BZOJ] 2427: [HAOI2010]软件安装

见7.3测试

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int MAXN=128;

int n,m;
int cost[MAXN],scost[MAXN];
int val[MAXN],sval[MAXN];

inline int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  return ret*f;
}

struct Edge{
  int to[MAXN],nxt[MAXN];
  int ecnt,head[MAXN];
  #define M(a) memset(a,0,sizeof(a))
  Edge(){M(to);M(nxt);M(head);ecnt=0;}
  #undef M
  void add(int x,int y){
    to[++ecnt]=y;
    nxt[ecnt]=head[x];
    head[x]=ecnt;
  }
}e1,e2;
int ind[MAXN];

int scc[MAXN],cnt;
int dfn[MAXN],low[MAXN],tim;
int sta[MAXN],ins[MAXN],top;
void tarjan(int x){
  dfn[x]=low[x]=++tim;
  ins[sta[++top]=x]=1;
  for(int i=e1.head[x];i;i=e1.nxt[i]){
    int v=e1.to[i];
    if(!dfn[v]) {tarjan(v);low[x]=min(low[x],low[v]);}
    else if(ins[v]) low[x]=min(low[x],dfn[v]);
  }
  if(dfn[x]==low[x]){
    int elm=-1;cnt++;
    while(elm!=x){
      ins[elm=sta[top--]]=0;
      scc[elm]=cnt;
      scost[cnt]+=cost[elm];
      sval[cnt]+=val[elm];
    }
  }
}

int f[128][512];
void dfs(int x){
   for(int i=e2.head[x];i;i=e2.nxt[i]){
     int v=e2.to[i];
     dfs(v);
     for(int j=m-scost[x];j>=0;j--)
       for(int k=0;k<=j;k++)
         f[x][j]=max(f[x][j],f[x][k]+f[v][j-k]);
   }
   for(int i=m;i>=0;i--)
     if(i>=scost[x]) f[x][i]=f[x][i-scost[x]]+sval[x];
     else f[x][i]=0;
}

int main(){
  n=rd();m=rd();
  for(int i=1;i<=n;i++) cost[i]=rd();
  for(int i=1;i<=n;i++) val[i]=rd();
  for(int i=1;i<=n;i++) e1.add(rd(),i);
  for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
  for(int i=1;i<=n;i++)
    for(int j=e1.head[i];j;j=e1.nxt[j]){
      int v=e1.to[j];
      if(scc[v]!=scc[i]) e2.add(scc[i],scc[v]),ind[scc[v]]++;
  }
  for(int i=1;i<=cnt;i++) if(!ind[i]) e2.add(cnt+1,i);
  dfs(cnt+1);
  cout<<f[cnt+1][m];
  return 0;
}