定睛一看，感觉跟选课貌似差不了太多诶…… 可是当我直接把我的 树形 DP+Tarjan 缩点 搞上去的时候却 WA 了一片
结果最后居然是数组大小的问题 QvQ….
那么我们正式进入主题。
上文已经说了，正解就是 Tarjan+树形 DP。
为什么要 Tarjan 来缩点呢？
想想，如果来了个环会发生什么……
会无限发生依赖！！！(然后就会出现一大片不堪入目的提交数据)
而对于这个环，要不就全选了，要不就都不选。
所以干脆缩成一个点好了~~~
Tarjan 过程：
inline void tarjan(int u){
low[u]=dfn[u]=++num;
hep[++top]=u;vis[u]=1;
for(register int i=head[u];i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to])tarjan(to),low[u]=min(low[u],low[to]);
else if(vis[to])low[u]=min(low[u],dfn[to]);
}if(dfn[u]==low[u]){
++tot;vis[u]=0;
while(hep[top+1]!=u)
fa[hep[top]]=tot,vis[hep[top--]]=0;
}return;
}//Tarjan 模板
树形 DP 片段：
inline void dp(int x){
for(register int i=cost[x];i<=m;++i)f[x][i]=val[x];
for(register int i=H[x];i;i=G[i].nxt){
int v=G[i].to;dp(v);
for(register int j=m-cost[x];j>=0;--j)
for(register int k=0;k<=j;++k)
f[x][j+cost[x]]=max(f[x][j+cost[x]],
f[x][j+cost[x]-k]+f[v][k]);
}return;
}
然后，读入数据，将每个点都用 Tarjan 搞一下 (已经属于某个强连通分量的就不搞了)，对于 Tarjan 后出现的每个点 (原来的或组成强连通分量的) 连边，最后通过新图跑树形 DP 即可。
建新图片段：
for(register int i=1;i<=n;++i)
if(!dfn[i])tarjan(i);
for(register int i=1;i<=n;++i){
val[fa[i]]+=v[i];cost[fa[i]]+=w[i];
if(fa[i]!=fa[up[i]]&&up[i])
addG(fa[up[i]],fa[i]),use[fa[i]]++;
}int s=tot+1;
for(register int i=1;i<=tot;++i)
if(!use[i])addG(s,i);
所以就 AC 了
代码：
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define Match
using namespace std;
const int N=3e2+10;
template <typename Tp> inline void read(Tp &x){
x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
}
struct Edge{int nxt,to;}edge[N<<1],G[N<<1];
int H[N],head[N],v[N],w[N],cost[N],val[N],f[N][N*5],cnt,C,tot,n,m;
int low[N],dfn[N],num,hep[N],top,vis[N],fa[N],up[N],use[N];
inline void addedge(int u,int v)
{edge[++cnt].nxt=head[u],edge[cnt].to=v,head[u]=cnt;}
inline void addG(int u,int v)
{G[++C].nxt=H[u],G[C].to=v,H[u]=C;}
inline void tarjan(int u){
low[u]=dfn[u]=++num;hep[++top]=u;vis[u]=1;
for(register int i=head[u];i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to])tarjan(to),low[u]=min(low[u],low[to]);
else if(vis[to])low[u]=min(low[u],dfn[to]);
}if(dfn[u]==low[u]){
++tot;vis[u]=0;
while(hep[top+1]!=u)
fa[hep[top]]=tot,vis[hep[top--]]=0;
}return;
}
inline void dp(int x){
for(register int i=cost[x];i<=m;++i)f[x][i]=val[x];
for(register int i=H[x];i;i=G[i].nxt){
int v=G[i].to;dp(v);
for(register int j=m-cost[x];j>=0;--j)
for(register int k=0;k<=j;++k)
f[x][j+cost[x]]=max(f[x][j+cost[x]],
f[x][j+cost[x]-k]+f[v][k]);
}return;
}
int main(){
ios::sync_with_stdio(false);
#ifndef Match
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
scanf("%d%d",&n,&m);
memset(f,-inf,sizeof(f));
for(register int i=1;i<=n;++i)scanf("%d",&w[i]);
for(register int i=1;i<=n;++i)scanf("%d",&v[i]);
for(register int x,i=1;i<=n;++i){
scanf("%d",&x);up[i]=x;
if(x)addedge(x,i);
}
for(register int i=1;i<=n;++i)
if(!dfn[i])tarjan(i);
for(register int i=1;i<=n;++i){
val[fa[i]]+=v[i];cost[fa[i]]+=w[i];
if(fa[i]!=fa[up[i]]&&up[i])
addG(fa[up[i]],fa[i]),use[fa[i]]++;
}int s=tot+1;
for(register int i=1;i<=tot;++i)
if(!use[i])addG(s,i);dp(s);
cost[s]=0;val[s]=0;
printf("%d\n",f[s][m+cost[s]]);
return 0;
}
0 条评论