我有两份代码,tarjan没写错,其他部分全部相同,只有dp的赋初值不同,为什么将取不到的dp值初始设为-INF能AC但设为0就会WA呢?求dalao解答!
dp部分如下:
int f[N][M], ind[N];
void dfs(int u) {
for (int j = 0; j <= m; ++j) f[u][j] = (j >= C[u] ? W[u] : -INF);
for (int i = Head[u]; i; i = E[i].pre) {
int v = E[i].to;
dfs(v);
for (int j = m; j >= C[u]; --j) {
for (int k = C[v]; k <= j; ++k) {
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
}
}
}
int f[N][M], ind[N];
void dfs(int u) {
for (int j = m; j >= C[u]; --j) f[u][j] = W[u];
for (int i = Head[u]; i; i = E[i].pre) {
int v = E[i].to;
dfs(v);
for (int j = m; j >= C[u]; --j) {
for (int k = C[v]; k <= j; ++k) {
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
}
}
}