C/C++数据结构——经商（并查集动规）

题目描述

小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

输入

1
5 3 7
5 10
3 2
4 3
1 100
1 2
2 3
1 4

输出

10

说明

小明能够接触到的人的编号有：2 3 4，那么对应接触编号为2的人花费5精力能够获得10的利益值是最优方案。
链接：https://ac.nowcoder.com/acm/problem/14348
来源：牛客网

解题代码

#include
struct men{
    int consume,make; 
}b[10005];
int link[10005];
int dp[505];
int find(int x)
{
    if(link[x]==x)return x;
    else 
		return link[x]=find(link[x]);
}
void merge(int x,int y)
{
	x=find(x);
	y=find(y);
    if(x==y) return;
    else
        link[y]=x;
        
    return;
}
int main()
{
    int T;
    int n,m,c;
    int x,y,k;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&c);
        memset(dp,0,sizeof(dp));
        for(int i=2;i<=n;i++){
            link[i]=i;
            scanf("%d%d",&b[i].consume,&b[i].make);
        }
        for(int i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            merge(x,y);
        }
        for(int i=2;i<=n;i++){
        	if(find(1)==find(i)){
        		for(int j=c;j>=b[i].consume;j--){
	                if(dp[j]<dp[j-b[i].consume]+b[i].make){
	                	dp[j]=dp[j-b[i].consume]+b[i].make;
					}
	            }
			}
            
        }
        printf("%d\n",dp[c]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

解题思路

首先是记录每个人认识的时候需要花费的精力和收货，然后并查集的思路，如果两个人能够认识就合并。合并之后动态规划去做就行了。