M_sea

洛谷2515 [HAOI2010]软件安装
Luogu分析需要注意的是,依赖可能会成环。显然,环内要么都选,要么都不选。然后就可以缩点,再建个虚点跑树上的分组...
扫描右侧二维码阅读全文
03
2018/11

洛谷2515 [HAOI2010]软件安装

Luogu

分析

需要注意的是,依赖可能会成环。

显然,环内要么都选,要么都不选。

然后就可以缩点,再建个虚点跑树上的分组背包。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=110;
const int MAXM=510;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int d[MAXN];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m;
int tmpw[MAXN],tmpv[MAXN];

int dfn[MAXN],low[MAXN];
int sta[MAXN],top=0,in[MAXN];
int belong[MAXN],w[MAXN],v[MAXN];
int dfs_clock=0,tot=0;

inline void Tarjan(int u) {
    low[u]=dfn[u]=++dfs_clock;
    sta[++top]=u,in[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]) {
        ++tot; int now;
        while (233) {
            now=sta[top--],in[now]=0;
            belong[now]=tot;
            w[tot]+=tmpw[now];
            v[tot]+=tmpv[now];
            if (now==u) break;
        }
    }
}

int f[MAXN][MAXM]; //f[i][j]表示以i为根的子树容量为j的最大价值 

inline void Dfs(int x) {
    for (re int i=w[x];i<=m;++i) f[x][i]=v[x];
    for (re int i=head[x];i;i=e[i].nxt) {
        int y=e[i].v; Dfs(y);
        for (re int i=m;i>=w[x];--i)
            for (re int j=0;j<=i-w[x];++j)
                f[x][i]=max(f[x][i],f[y][j]+f[x][i-j]);
    }
}

int ind[MAXN];

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) tmpw[i]=read();
    for (re int i=1;i<=n;++i) tmpv[i]=read();
    for (re int i=1;i<=n;++i) {
        d[i]=read();
        if (d[i]) addEdge(d[i],i);
    }
    for (re int i=1;i<=n;++i)
        if (!dfn[i]) Tarjan(i);
    cnt=0; memset(head,0,sizeof(head));
    for (re int i=1;i<=n;++i) {
        if (!d[i]) continue;
        int u=belong[d[i]],v=belong[i];
        if (u!=v) { addEdge(u,v); ++ind[v]; }
    }
    for (re int i=1;i<=tot;++i)
        if (!ind[i]) addEdge(0,i);
    Dfs(0);
    printf("%d\n",f[0][m]);
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 52 PM

发表评论