洛谷P2515 [HAOI2010]软件安装（tarjan缩点+树上背包）

传送门

看题面非常容易想到：有依赖的树上背包问题。在给有向图且存在环的情况下（即多个软件互相依赖，只能同时选择装或不装），用 $tarjan$ 缩成有向树处理。

由于对于任意一个结点，若不选则其所有后代都不能选，得到状态转移方程

$dp[x][j+k]=max(dp[x][j+k],dp[x][j]+dp[to][k])$

一份 $vector$ 想不通哪里写挂只有 $80$ 分，怒而转战链式前向星的代码

#include <bits/stdc++.h>
using namespace std;
struct Edge
{
    int next;
    int to;
}edge[105],e[105];
int head[105];
int h[105];
int cot=1;
int cnt=1;
void init(){
    memset(head,-1,sizeof(head));
    memset(h,-1,sizeof(h));
    cnt=1;
    cot=1;
}
void adde(int l,int r){
    e[cot].next=h[l];
    e[cot].to=r;
    h[l]=cot++;
}
void add(int l,int r){
    edge[cnt].next=head[l];
    edge[cnt].to=r;
    head[l]=cnt++;
}

int n,m;
int w[105],v[105],nv[105],nw[105];
int posi[105];
int co=0;
int dfn[105],low[105];
int dp[105][505];
int x=0,tmp=0;
bool used[105];
int s[105];
stack<int> st;

void tarjan(int u){
	dfn[u]=low[u]=++x;
	st.push(u);
	
	for(int i=head[u];i!=-1;i=edge[i].next){
        int to=edge[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[u]=min(low[u],low[to]);
		}
		else if(!posi[to])
			low[u]=min(low[u],dfn[to]);
	}
	
	if(dfn[u]==low[u]){
		co++;
		do{
			tmp=st.top();
			st.pop();
			posi[tmp]=co;
            nv[co]+=v[tmp];
            nw[co]+=w[tmp];
		}
		while(u!=tmp);
	}
}

void dfs(int x){
    s[x]=nw[x];
    dp[x][nw[x]]=nv[x];
    for(int i=h[x];i!=-1;i=e[i].next){
        int to=e[i].to;
        dfs(to);
        for(int j=s[x];j>=nw[x];j--){
            for(int k=0;k<=s[to];k++){
                if(j+k>m)
                    break;
                dp[x][j+k]=max(dp[x][j+k],dp[x][j]+dp[to][k]);
            }
        }
        s[x]+=s[to];
    }
}

signed main(){
    cin>>n>>m;
    init();
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<=n;i++)
        cin>>v[i];
    for(int i=1;i<=n;i++){
        int f;
        cin>>f;
        if(f)
            add(f,i);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);

    for(int i=1;i<=n;i++){
        for(int j=head[i];j!=-1;j=edge[j].next){
            int to=edge[j].to;
            if(posi[to]!=posi[i]){
                adde(posi[i],posi[to]);
                used[posi[to]]=1;	
            }
        }
    }
    for(int i=1;i<=co;i++)
        if(!used[i])
            adde(0,i);
    dfs(0);
    int ans=0;
    for(int i=0;i<=m;i++)
        ans=max(ans,dp[0][i]);
    cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120