定睛一看,感觉跟选课貌似差不了太多诶…… 可是当我直接把我的 树形 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;
}
我居然因为 f 数组开小了调了两个多小时…..
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

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