B-经商 (nowcoder.com)

题目描述

小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能够获得的最大利益值

链接:https://ac.nowcoder.com/acm/problem/14545 来源:牛客网

示例1

输入

复制

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

输出

复制

10

题意解析

由题意比如1认识2,2认识3,那么1就可以接触3进行交际,当然1和2也可以交际。可知此题需要运用并查集知识进行分类,找到1能够联系到的人,然后再运用01背包模板直接求解最大价值.

并查集的查找+按节点个数进行合并(比普通合并更快)+01背包 12ms

AC代码

#include <bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(0);
const int maxn=1e4+5;
int pre[maxn],num[maxn];
int dp[505];
int w[maxn],v[maxn];
int n,m,c;
void init(int n){
    for(int i=1;i<=n;++i){
        pre[i]=i;
        num[i]=1;
    }
}
int find(int x){
    if(pre[x]==x)
        return x; 
    return pre[x] = find(pre[x]);
}
void merge(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx==fy)
        return;
    if(num[fx]>num[fy])//fy的节点数更多
        swap(fx,fy);
    pre[fx]=fy;
    num[fy]+=num[fx];
}
void zeroonepack(int w,int v){//容量,价值   
	for(int i=c;i>=w;i--)//最大容量,
		dp[i]=max(dp[i],dp[i-w]+v);
}
int main(){
    IOS;
    int t;cin>>t;
    while(t--){
        cin>>n>>m>>c;
        init(n);
        for(int i=2;i<=n;++i){
            cin>>w[i]>>v[i];
        }
        for(int i=1;i<=m;++i){
            int a,b;
            cin>>a>>b;
            merge(a,b);
        }
        memset(dp,0,sizeof dp);
        for(int i=2;i<=n;++i){
            if(find(i)==find(1)){
                zeroonepack(w[i],v[i]);
            }
        }
        cout<<dp[c]<<endl;
    }
    return 0;
}