并查集、01背包

题意：

小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。

小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。

小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。

小d想知道，他在精力范围内，能够获得的利益值到底是多少。

设定小d自己的编号为1.并且对应一个人的交际次数限定为1.

输入描述:
本题包含多组输入，第一行输入一个数t，表示测试数据的组数
每组数据的第一行输入三个数，N,M，C，表示这个人际关系网一共有多少个人，关系网的关系数，以及小d的精力值
接下来N-1行，每行两个数ai，bi。这里第i行表示和编号为i+1的人认识需要花费ai的精力，能够获得的利益值为bi。
再接下来M行，每行两个数x，y，表示编号为x的人能够和编号为y的人接触
t<=50
2<=N<=10000
1<=M<=10*N
1<=ai，bi<=10
1<=C<=500
1<=x,y<=N
输出描述:
输出包含一行，表示小d能够获得的最大利益值

分析

这题并不难，我们先用并查集，划一下分块，再筛选出与节点1在一个分块的其他节点，对这些节点使用01背包动态规划就行了。
代码如下，注意细节

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int max_n = 10100;
int n, m, c;
int a[max_n];
int b[max_n];
int root[max_n];
int dp[550];

int find(int x) {
    return (root[x] == x ? x : root[x] = find(root[x]));
}

void merge(int x, int y) {
    root[find(x)] = find(y);
}

int main() {
    ios::sync_with_stdio(0);
    int t;cin >> t;
    while (t--) {
        cin >> n >> m >> c;
        fill(dp, dp + c + 1, 0);
        for (int i = 1;i <= n;i++)root[i] = i;
        for (int i = 2;i <= n;i++)
            cin >> b[i] >> a[i];
        int x, y;
        for (int i = 0;i < m;i++) {
            cin >> x >> y;merge(x, y);
        }
        vector<int> bag;
        for (int i = 2;i <= n;i++)
            if (find(i) == find(1))
                bag.push_back(i);
        for (int i = 0;i < bag.size();i++)
            for (int j = c;j >= b[bag[i]];j--)
                    dp[j] = max(dp[j], dp[j - b[bag[i]]] + a[bag[i]]);
        cout << dp[c] << endl;
    }
}

这道题中，我用了滚动数组，需要注意的是，使用滚动数组需要从后往前遍历，因为如果从前往后遍历的话，那么对于后面的格点，用于推出他的前面的格点很有可能已经被改了。
一直懒省事，没大用过滚动数组。