目录
B-经商
题目描述:
输入描述:
输出描述:
输入
输出
实现代码与解析:
并查集 + 01背包
原理思路:
B-经商
链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
题目描述:
小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
实现代码与解析:
并查集 + 01背包
import java.util.Scanner;public class Main {public static int[] p = new int[10010];public static int find(int x) {if (x != p[x]) p[x] = find(p[x]);return p[x];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();while (t-- > 0) {int n = sc.nextInt();int m = sc.nextInt();int c = sc.nextInt();int[] w = new int[n + 1]; // 消耗的精力int[] v = new int[n + 1]; // 获得的精力for (int i = 2; i < n + 1; i++) {int a = sc.nextInt();int b = sc.nextInt();w[i] = a;v[i] = b;}for (int i = 0; i < n + 1; i++) {p[i] = i;}for (int i = 0; i < m; i++) {int a = sc.nextInt();int b = sc.nextInt();p[find(a)] = find(b);}int[] f = new int[c + 1];for (int i = 2; i < n + 1; i++) {for (int j = c; j >= w[i] && find(1) == find(i); j--) {f[j] = Math.max(f[j], f[j - w[i]] + v[i]);}}System.out.println(f[c]);}}
}
原理思路:
简单的01背包问题,不过选择物品时,不一定能选,因为不一定联通,所以用并查集判断一下即可。
并查集详解:
Leetcode:684. 冗余连接(并查集C++)_树可以看成是一个连通且无环的无向图。 给定往一棵 n 个节点 (节点值 1~n) 的树-CSDN博客
背包详解:
动态规划:0-1背包、完全背包问题 | 详细原理解释 | 代码及优化(C++)_c++ 01背包问题时间优化-CSDN博客