BZOJ 2427: [HAOI2010]软件安装 tarjan + 树形背包

迈不过友情╰ 2021-11-17 16:18 268阅读 0赞

Code:

#include<bits/stdc++.h>
    using namespace std;  
    #define setIO(s) freopen(s".in","r",stdin)  
    #define maxn 600 
    int edges,n,m; 
    int w[maxn],cost[maxn],hd[maxn],to[maxn<<1],nex[maxn<<1],val[maxn];    
    void addedge(int u,int v)
    {
        nex[++edges]=hd[u],hd[u]=edges,to[edges]=v; 
    }
    map<int,int>M[maxn]; 
    int num,scc;  
    vector<int>G[maxn]; 
    stack<int>S; 
    int dfn[maxn],low[maxn],W[maxn],V[maxn],idx[maxn],vis[maxn];   
    void tarjan(int u) 
    {
        low[u]=dfn[u]=++scc,vis[u]=1; 
        S.push(u); 
        for(int i=hd[u];i;i=nex[i]) 
        {
            int v=to[i]; 
            if(!vis[v]) tarjan(v), low[u]=min(low[u],low[v]); 
            else if(vis[v]==1) low[u]=min(low[u],dfn[v]); 
        }
        if(low[u]==dfn[u]) 
        {
            ++num; 
            for(;;) 
            {
                int x=S.top(); S.pop();
                vis[x]=-1;  
                W[num]+=cost[x], V[num]+=val[x], idx[x]=num; 
                if(x==u) break;            
            }
        }
    }
    int f[maxn][1200],tmp[maxn][1200],du[maxn];   
    void solve(int x) 
    {    
        for(int i=W[x];i<=m;++i) f[x][i]=V[x];      
        for(int i=0;i<G[x].size();++i)
        {
            int v=G[x][i]; 
            solve(v); 
            for(int j=m-W[x];j>=0;--j) 
            {
                for(int q=0;q<=j;++q) 
                { 
                    f[x][W[x]+j]=max(f[x][W[x]+j], f[x][W[x]+j-q] + f[v][q]);   
                }
            }
        }
    }
    int main()
    { 
        int i,j; 
        // setIO("input");  
        scanf("%d%d",&n,&m); 
        for(i=1;i<=n;++i) scanf("%d",&cost[i]); 
        for(i=1;i<=n;++i) scanf("%d",&val[i]); 
        for(i=1;i<=n;++i) 
        {
            int x; 
            scanf("%d",&x); 
            addedge(x,i);              
        }
        for(i=1;i<=n;++i) if(!vis[i]) tarjan(i); 
        for(i=1;i<=n;++i) 
        {
            int cur=idx[i]; 
            for(j=hd[i];j;j=nex[j]) 
            { 
                int v=idx[to[j]];   
                if(cur!=v&&!M[cur][v]) 
                {
                    M[cur][v]=1;   
                    G[cur].push_back(v); 
                    ++du[v];  
                }
            }
        }
        for(i=1;i<=num;++i) if(du[i]==0) G[0].push_back(i); 
        solve(0); 
        printf("%d\n",f[0][m]); 
        return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11191810.html