【练习】B-经商

---

题目

---

题目描述：
小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。
小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
输出描述：
输出包含一行，表示小d能够获得的最大利益值

---

解析

---

1）知识点

2）看题目

3）算法分析

4）算法操作

5）打代码

---

AC代码

---

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e4 + 7;
int N, M, C;
int fa[MAX], cost[MAX], val[MAX];
int dp[MAX];
//全局变量区

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) fa[x] = y;
}
//函数预定义区

int main() {
    IOS;
    int T; cin >> T;
    while (T--) {
        cin >> N >> M >> C;
        for (int i = 1; i <= N; i++) fa[i] = i;
        for (int i = 2; i <= N; i++) cin >> cost[i] >> val[i];
        for (int i = 1; i <= M; i++) {
            int u, v; cin >> u >> v;
            merge(u, v);
        }
        memset(dp, 0, sizeof dp);
        for (int i = 2; i <= N; i++) 
            if (find(i) == find(1))
                for (int j = C; j >= cost[i]; j--)
                    dp[j] = max(dp[j], dp[j - cost[i]] + val[i]);
        cout << dp[C] << endl;
    }
    return 0;
}
//函数区