题解 | #经商#

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

题目描述

思路：普通的并查集+01背包的题目，是一道基础题

看到要构造与1能够连通的关系图，就能想到用并查集实现

看到要求最大值，就能想到三种解法：贪心，动态规划，二分。

贪心的话，由于要同时考虑两个值（消耗的精力与获得的利益）的动态变化，所以可以首先排除

由于前面分析出来要考虑两个值的动态变化，所以试试看动态规划。

动态规划的话，注意题干最后一句“并且对应一个人的交际次数限定为1”，也就是每一组数据只能用1次，然后看看每组数据的值，一个是消耗的精力值，一个是获得的利益，求的是利益最大值。

再看01背包问题：一个背包（总精力值）和一系列物品（一堆可以接触的人），每个物品（人）都有自己的重量（消耗的精力值）和价值（利益值）。目标是确定哪些物品（人）应该被包括在背包中，以便背包中的物品总价值（总利益值）最大，同时不超过背包的容量限制（精力值总消耗不超过总精力值）。

所以考虑01背包

二分没试过，但是好像不行，因为二分在0~总利益值内二分取值之后，似乎不能直接求出来，比如说对于这个题目的样例来说，要在0~15之间二分（取0是为了防止精力不够与任何一个人交际的情况），获得一个值之后，对于如何求这个值还是比较麻烦。

代码如下：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int father[10020];
struct ss{
    int a,b;
}d[10020];
int aa[10020],bb[10020],f[10020]; //aa为消耗的精力值，bb为获得的价值，f[i]表示总消耗精力值为i的情况下，能够获得的最大利益 
int find(int x){ //查找函数
    if(father[x]==x) return x;
    else return father[x]=find(father[x]);
}
void merge(int a,int b){ //合并函数
    if(find(a)!=find(b)) father[find(a)]=find(b);
}
int main(){
    int T,n,m,c,x,y;
    scanf("%d",&T);
    while(T--){
        memset(aa,0,sizeof(aa));
        memset(bb,0,sizeof(bb));
        memset(f,0,sizeof(f)); //一定记得清空f数组，这句不加只能过60%的样例
        scanf("%d %d %d",&n,&m,&c);
        father[1]=1;
        for(int i=2;i<=n;i++){
            scanf("%d %d",&d[i].a,&d[i].b);
            father[i]=i;
        }
        while(m--){ 
            scanf("%d %d",&x,&y);
            merge(x,y);
        }
        int p=1;
        for(int i=2;i<=n;i++){
            if(find(i)==find(1)){ //如果1的父节点与i的父节点相同（即i的父节点为1），那么将这个节点的值存入aa与bb中，供后面使用
                aa[p]=d[i].a;
                bb[p]=d[i].b;
                p++;
            }
        }
        for(int i=1;i<p;i++){ //01背包模板，用了一维数组节省空间，注意用一维数组时，内层循环要逆序
            for(int j=c;j>=aa[i];j--){
                f[j]=max(f[j],f[j-aa[i]]+bb[i]);
            }
        }
        printf("%d\n",f[c]); //f[c]即为要求的值
    }
    return 0;
}