NC 14545 DFS + DP

题意

传送门 NC 14545

题解

$DFS$ 求节点 $1$ 的所有连通节点，$DP$ 求解背包问题。

#include <bits/stdc++.h> using namespace std; #define maxn 10005 #define maxc 505 typedef long long ll; int N, M, C, a[maxn], b[maxn], used[maxn], dp[maxc]; vector<int> G[maxn], net; void dfs(int u) { net.push_back(u); used[u] = 1; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (!used[v]) dfs(v); } } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d%d", &N, &M, &C); G[1].clear(); for (int i = 2; i <= N; i++) { scanf("%d%d", a + i, b + i); G[i].clear(); } for (int i = 0; i < M; i++) { int x, y; scanf("%d%d", &x, &y); G[x].push_back(y); G[y].push_back(x); } net.clear(); memset(used, 0, sizeof(used)); memset(dp, 0, sizeof(dp)); dfs(1); for (int i = 0; i < net.size(); i++) { int id = net[i]; for (int j = C; j >= a[id]; j--) { dp[j] = max(dp[j], dp[j - a[id]] + b[id]); } } printf("%d\n", *max_element(dp, dp + C + 1)); } return 0; }