P2515-[HAOI2010]软件安装

  1 #include <iostream>
  2 #include <vector>
  3 #define _for(i,a,b) for(register int i = (a);i < b;i ++)
  4 #define _rep(i,a,b) for(register int i = (a);i > b;i --)
  5 #define INF 0x3f3f3f3f
  6 #define MOD 100000000
  7 #define maxn 1503
  8 #define pb push_back
  9 #define debug() printf("Miku Check OK!
")
 10 typedef long long ll;
 11 
 12 using namespace std;
 13 typedef pair<int,int> P;
 14 inline ll read()
 15 {
 16     ll ans = 0;
 17     char ch = getchar(), last = ' ';
 18     while(!isdigit(ch)) last = ch, ch = getchar();
 19     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
 20     if(last == '-') ans = -ans;
 21     return ans;
 22 }
 23 inline void write(ll x)
 24 {
 25     if(x < 0) x = -x, putchar('-');
 26     if(x >= 10) write(x / 10);
 27     putchar(x % 10 + '0');
 28 }
 29 int N,M;
 30 int ver[maxn],Next[maxn],head[maxn],dfn[maxn],low[maxn];
 31 int Gver[maxn],GNext[maxn],Ghead[maxn],Gtot;
 32 int stack[maxn],ins[maxn],c[maxn];
 33 vector<int> scc[maxn];
 34 int tot,top,cnt,nm;
 35 int We[maxn],Ve[maxn],W[maxn],V[maxn];
 36 int iopW[maxn],iopV[maxn],iopD[maxn];
 37 int indeg[maxn];
 38 int dp[maxn][maxn];
 39 void addori(int x,int y)
 40 {
 41     ver[++tot] = y,Next[tot] = head[x],head[x] = tot;
 42 }
 43 void tarjan(int x)
 44 {
 45     dfn[x] = low[x] = ++nm;
 46     stack[++top] = x,ins[x] = 1;
 47     for(int i = head[x]; i; i = Next[i])
 48     {
 49         int y = ver[i];
 50         if(!dfn[y])
 51         {
 52             tarjan(y);
 53             low[x] = min(low[x],low[y]);
 54         }
 55         else if(ins[y])
 56             low[x] = min(low[x],dfn[y]);
 57     }
 58     if(dfn[x] == low[x])
 59     {
 60         cnt ++;
 61         int y;
 62         do
 63         {
 64             y = stack[top --],ins[y] = 0;
 65             c[y] = cnt,scc[cnt].pb(y);
 66         }
 67         while(x != y);
 68     }
 69 }
 70 void addAft(int x,int y)
 71 {
 72     Gver[++Gtot] = y;
 73     GNext[Gtot] = Ghead[x];
 74     Ghead[x] = Gtot;
 75 }
 76 void Shrink()
 77 {
 78     _for(i,1,N+1)
 79     if(!dfn[i])
 80         tarjan(i);
 81 
 82     _for(x,1,N+1)
 83     for(int i = head[x]; i; i = Next[i])
 84     {
 85         int y = ver[i];
 86         if(c[x]==c[y]) continue;
 87         addAft(c[y],c[x]);
 88         indeg[c[x]] ++;
 89     }
 90     _for(i,1,cnt+1)
 91     _for(j,0,scc[i].size())
 92     W[i] += We[scc[i][j]],V[i] += Ve[scc[i][j]];
 93 
 94     _for(i,1,cnt+1)
 95     if(!indeg[i])
 96         addAft(0,i);
 97 }
 98 void dfs(int u)
 99 {
100     _for(i,W[u],M+1)
101         dp[u][i] = V[u];
102     for(int p = Ghead[u]; p; p = GNext[p])
103     {
104         int y = Gver[p];
105         dfs(y);
106         int k = M - W[u];
107         _rep(i,k,-1)
108             _for(j,0,i+1)
109                 dp[u][i + W[u]] = max(dp[u][i + W[u]],
110                                      dp[y][j] + dp[u][i + W[u] - j]);
111     }
112 }
113 int main()
114 {
115     N = read();
116     M = read();
117     _for(i,1,N+1)
118     iopW[i] = read();
119     _for(i,1,N+1)
120     iopV[i] = read();
121     _for(i,1,N+1)
122     iopD[i] = read();
123 
124     _for(i,1,N+1)
125     {
126         We[i] = iopW[i];
127         Ve[i] = iopV[i];
128         if(iopD[i])
129             addori(i,iopD[i]);
130     }
131     Shrink();
132     dfs(0);
133     write(dp[0][M]);
134     return 0;
135 }