牛客，并查集，简单dp经商

链接：https://ac.nowcoder.com/acm/problem/14545

来源：牛客网

题目描述

小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

输入

输出

10
并查集裸题，加了一个dp
先找1可以和谁交际，之后计算一下最大值即可
代码：

 1 #include<bits/stdc++.h>
 2 #define maxn 100010
 3 
 4 using namespace std;
 5 
 6 int fa[maxn];
 7 int t;
 8 struct node{
 9     int x,y;
10 }a[maxn];
11 int dp[maxn];
12  
13 int find(int x){return x==fa[x]? x:fa[x]=find(fa[x]);}
14 
15 void Union(int x,int y)
16 {
17     int fx=find(x),fy=find(y);
18     if(fx!=fy) 
19       fa[fx]=fy;
20     return ;
21 }
22 
23 void solve()
24 {
25     int n,m,c;
26     memset(dp,0,sizeof(dp));
27     for(int i=1; i<=maxn-5; i++) fa[i]=i;
28     
29     scanf("%d%d%d",&n,&m,&c);
30     for(int i=2 ;i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y);
31     for(int i=1; i<=m; i++) 
32     {
33      int x,y;
34      scanf("%d%d",&x,&y);
35      //if(x>y) swap(x,y);
36      Union(x,y);
37     }
38     
39     for(int i=2; i<=n ;i++)
40      {
41          if(find(i)==find(1))
42          {
43              int fy=a[i].y;
44             int fx=a[i].x;
45              for(int j=c;j>=fx;j--)
46              {
47                  dp[j]=max(dp[j-fx]+fy,dp[j]);//花费当前精力所得到的收益 
48              }
49          //for(int jj=0;jj<=c;jj++){
50               //cout<<dp[jj]<<" ";
51           }
52      }
53      printf("%d\n",dp[c]);//花费c个精力得到的最大收益 
54      return ;
55  } 
56 int main()
57 {
58     scanf("%d",&t);
59     while(t--)
60     {
61         solve();
62     }
63     return 0;
64  }

#include<bits/stdc++.h>
#define maxn 100010

using namespace std;

int fa[maxn];
int t;
struct node{
    int x,y;
}a[maxn];
int dp[maxn];
 
int find(int x){return x==fa[x]? x:fa[x]=find(fa[x]);}

void Union(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy) 
      fa[fx]=fy;
    return ;
}

void solve()
{
    int n,m,c;
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=maxn-5; i++) fa[i]=i;
    
    scanf("%d%d%d",&n,&m,&c);
    for(int i=2 ;i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1; i<=m; i++) 
    {
     int x,y;
     scanf("%d%d",&x,&y);
     //if(x>y) swap(x,y);
     Union(x,y);
    }
    
    for(int i=2; i<=n ;i++)
     {
         if(find(i)==find(1))
         {
             int fy=a[i].y;
            int fx=a[i].x;
             for(int j=c;j>=fx;j--)
             {
                 dp[j]=max(dp[j-fx]+fy,dp[j]);//花费当前精力所得到的收益 
             }
         //for(int jj=0;jj<=c;jj++){
              //cout<<dp[jj]<<" ";
          }
     }
     printf("%d\n",dp[c]);//花费c个精力得到的最大收益 
     return ;
 } 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
    return 0;
}