水题笔记_ HAOI2010 软件安装 [树形DP, Tarjan]

有环的图可以考虑缩点转化成树

懵逼的 题目

传送至 BZOJ

扯淡的 题解

乍一看woc这不是选课嘛? 还省选?(flag * 1)
然后他们说可能会有环要用缩点
emmmm…那也很水啊把两个程序拼起来就行了(flag * 2)
然后…
20
发现没有处理 [当前节点不能选但是兄弟可以选] 的情况(选课的话因为费用都是 1 不会GG)
40
发现没有处理好环…没有把缩完点的环和 root 连起来

剩下就没什么好说的了…
就是选课魔改 × tarjan缩点

沙茶的 代码

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define MAXN (100 + 5)
#define MAXM (500 + 5)
#define MAXW (100000 + 5)
#define MAXV (50000 + 5)
#define INF (10000000 + 5)
#define MNULL (100 + 3)
const int root = 0;
using namespace std;
struct edg
{
int from;
int to;
int next;
} b[MAXN];
int g[MAXN];
int cntb;

struct node
{
int right;
int left;
} a[MAXN];

int n;
int m;
int w[MAXN];
int v[MAXN];

int fa[MAXN];
int wn[MAXN];
int vn[MAXN];

int dfn[MAXN];
int low[MAXN];
int cntd;
stack<int> s;
bool instack[MAXN];

int ans;

int f[MAXN][MAXV];

void init();
void adn(int, int);
void tarjan(int);
void inite();
void adnn(int, int);
void solve();
int dfs(int, int);
int main()
{
init();
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
{
tarjan(i);
}
}
inite();
solve();
printf("%d", ans);
return 0;
}

void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
g[from] = cntb;
}

void init()
{
memset(instack, false, sizeof(instack));
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++)
{
a[i].left = a[i].right = MNULL;
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &v[i]);
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
}
int srx;
for (int i = 1; i <= n; i++)
{
scanf("%d", &srx);
adn(srx, i);
}
}

void tarjan(int dq)
{
low[dq] = dfn[dq] = ++cntd;
s.push(dq);
instack[dq] = true;
for (int i = g[dq]; i; i = b[i].next)
{
if (!dfn[b[i].to])
{
tarjan(b[i].to);
low[dq] = min(low[dq], low[b[i].to]);
}
else if (instack[b[i].to])
{
low[dq] = min(low[dq], dfn[b[i].to]);
}
}
if (low[dq] == dfn[dq])
{
while (!s.empty() && s.top() != dq)
{
int& x = s.top();
fa[x] = dq;
instack[x] = false;
s.pop();
}
if (!s.empty())
{
s.pop();
fa[dq] = dq;
instack[dq] = false;
}
}
}

void inite()
{
bool visited[MAXN];
memset(visited, false , sizeof(visited));
for (int i = 1; i <= n; i++)
{
vn[fa[i]] += v[i];
wn[fa[i]] += w[i];
if (fa[b[i].from] != fa[b[i].to])
{
adnn(fa[b[i].from], fa[b[i].to]);
visited[fa[b[i].to]] = true;
}
}
for (int i = 1; i <= n; i++)
{
if (!visited[fa[i]])
{
adnn(0, fa[i]);
visited[fa[i]] = true;
}
}
}

void adnn(int from, int to)
{
if (a[from].left == MNULL)
{
a[from].left = to;
}
else
{
int x;
x = a[from].left;
while (a[x].right != MNULL)
{
x = a[x].right;
}
a[x].right = to;
}
}

void solve()
{
memset(f, -1, sizeof(f));
/*for (int i = 0; i <= m; i++)
{
f[root][i] = 0;
}*/
/*for (int i = 1; i <= m; i++)
{
ans = max(ans, dfs(root, i));
}*/
ans = dfs(root, m);
}

int dfs(int dq, int dqm)
{
if (dqm < 0)// dqm < 0: GG
{
return -INF;
}
if (f[dq][dqm] != -1)// 已经访问过
{
return f[dq][dqm];
}
if (dq == MNULL || (dqm == 0 && vn[dq] != 0))// 访问到空, 或者dqm == 0
{
return f[dq][dqm] = 0;
}
f[dq][dqm] = (dqm >= vn[dq]) ? wn[dq] : 0;// 能否选当前节点
f[dq][dqm] = max(f[dq][dqm], dfs(a[dq].right, dqm));// 全部都选兄弟
if (dqm >= vn[dq])
{
f[dq][dqm] = max(f[dq][dqm], dfs(a[dq].left, dqm - vn[dq]) + wn[dq]);// 全部都选儿子
for (int i = 0; i <= dqm - vn[dq]; i++)
{
f[dq][dqm] = max(f[dq][dqm], dfs(a[dq].left, i) + dfs(a[dq].right, dqm - vn[dq] - i) + wn[dq]);// i 个选儿子, 剩下的选兄弟, 当然还要选自己
}
}
return f[dq][dqm];
}

/*
3 10
5 5 6
2 3 4
0 1 1


5
*/

/*
8 6
5 2 1 1 2 3 10 1
1 5 6 7 8 5 1 8
0 1 1 2 2 2 3 0


9
*/


/*
6 20
5 5 5 1 10 5
1 1 1 100 5 5
2 3 1 2 0 5


103
*/

By 逃课一时爽的 Cansult

附: 我们今天语文连堂老师不在, 就变成一节正课一节活动课, 本来想逃活动课结果逃了正课…CTL