题意
传送门 NC 14545
题解
D F S DFS DFS 求节点 1 1 1 的所有连通节点, D P DP 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;
}