NC14545 经商

用并查集把有关系的人并在一起，采用动态规划求最大值

#include <iostream>
#include <queue>
using namespace std;
const int maxn = 10010;
struct node {
    int pre;
    int val;
    int jingli;
}arr[maxn];
int dp[maxn];
void init() {
    for (int i = 0; i <maxn; i++) {
        arr[i].pre = i;
        arr[i].val = 0;
        arr[i].jingli = 0;
    }
}
int find(int num) {
    return num == arr[num].pre ? num : find(arr[num].pre);
}
void merge_set(int num1,int num2) {
    int fa = find(num1);
    int fb = find(num2);
    if (fa != fb)arr[fb].pre = fa;
}
int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n, m, c;
        cin >> n >> m >> c;
        init();
        for (int i = 2; i <= n; i++) {
            cin >> arr[i].jingli >> arr[i].val;
        }
        for (int i = 0; i < m; i++) {
            int num1, num2;
            cin >> num1 >> num2;
            merge_set(num1, num2);
        }
        for(int i=0;i<maxn;i++){
            dp[i]=0;
        }
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            if (find(i) == find(1)) {
                for (int j = c; j >= arr[i].jingli; j--) {
                    dp[j] = max(dp[j], dp[j - arr[i].jingli] + arr[i].val);
                }
            }
        }
        cout << dp[c]<<endl;
    }
}