题目
题目描述:小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背包问题。
2)看题目
- 题目的意思就是小d会和自己认识的人,或者自己认识的人认识的人交流。
- 小d很功利,在保证自己精力不透支的情况下交到总利益和最大的一些朋友。
3)算法分析
- 首先我们可以用并查集给每个人划分区块。
- 然后用01背包进行选择就好。
- 并查集依旧是查找和合并就行了。
- 01背包只要在找到了和小d同一区块的人时计算就好了。
4)算法操作
- 首先是并查集的查找与合并:
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; }
- 然后就是对同区块的查找了:
for (int i = 2; i <= N; i++) if (find(i) == find(1))
- 01背包进行dp就是套路了:
for (int j = C; j >= cost[i]; j--) dp[j] = max(dp[j], dp[j - cost[i]] + val[i]);
- 查找与背包合并起来就是这样的:
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]);
5)打代码
- 所以我们先输入数据。
- 然后合并区间,建立并查集。
- 接下来查找+dp就好啦。
- 下面全代码~
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; } //函数区