首页 > 代码库 > HDU 5242 Game（三个贪心）
HDU 5242 Game（三个贪心）
Game
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1385 Accepted Submission(s): 452
Problem Description
It is well known that Keima Katsuragi is The Capturing God because of his exceptional skills and experience in ‘‘capturing‘‘ virtual girls in gal games. He is able to play k games simultaneously.
One day he gets a new gal game named ‘‘XX island‘‘. There are n scenes in that game, and one scene will be transformed to different scenes by choosing different options while playing the game. All the scenes form a structure like a rooted tree such that the root is exactly the opening scene while leaves are all the ending scenes. Each scene has a value , and we use wi as the value of the i-th scene. Once Katsuragi entering some new scene, he will get the value of that scene. However, even if Katsuragi enters some scenes for more than once, he will get wi for only once.
For his outstanding ability in playing gal games, Katsuragi is able to play the game k times simultaneously. Now you are asked to calculate the maximum total value he will get by playing that game for k times.
One day he gets a new gal game named ‘‘XX island‘‘. There are n scenes in that game, and one scene will be transformed to different scenes by choosing different options while playing the game. All the scenes form a structure like a rooted tree such that the root is exactly the opening scene while leaves are all the ending scenes. Each scene has a value , and we use wi as the value of the i-th scene. Once Katsuragi entering some new scene, he will get the value of that scene. However, even if Katsuragi enters some scenes for more than once, he will get wi for only once.
For his outstanding ability in playing gal games, Katsuragi is able to play the game k times simultaneously. Now you are asked to calculate the maximum total value he will get by playing that game for k times.
Input
The first line contains an integer T(T≤20), denoting the number of test cases.
For each test case, the first line contains two numbers n,k(1≤k≤n≤100000), denoting the total number of scenes and the maximum times for Katsuragi to play the game ‘‘XX island‘‘.
The second line contains n non-negative numbers, separated by space. The i-th number denotes the value of the i-th scene. It is guaranteed that all the values are less than or equal to 231−1.
In the following n−1 lines, each line contains two integers a,b(1≤a,b≤n), implying we can transform from the a-th scene to the b-th scene.
We assume the first scene(i.e., the scene with index one) to be the opening scene(i.e., the root of the tree).
For each test case, the first line contains two numbers n,k(1≤k≤n≤100000), denoting the total number of scenes and the maximum times for Katsuragi to play the game ‘‘XX island‘‘.
The second line contains n non-negative numbers, separated by space. The i-th number denotes the value of the i-th scene. It is guaranteed that all the values are less than or equal to 231−1.
In the following n−1 lines, each line contains two integers a,b(1≤a,b≤n), implying we can transform from the a-th scene to the b-th scene.
We assume the first scene(i.e., the scene with index one) to be the opening scene(i.e., the root of the tree).
Output
For each test case, output ‘‘Case #t:‘‘ to represent the t-th case, and then output the maximum total value Katsuragi will get.
Sample Input
25 24 3 2 1 11 21 52 32 45 34 3 2 1 11 21 52 32 4
Sample Output
Case #1: 10Case #2: 11
Source
The 2015 ACM-ICPC China Shanghai Metropolitan Programming Contest
Recommend
/** @Author: lyuc* @Date: 2017-04-29 19:33:34* @Last Modified by: lyuc* @Last Modified time: 2017-04-29 21:16:49*//* 题意：一棵树有n个节点，每个节点有一个价值。一个人从根节点走到某叶子节点算一次游戏，可以 * 获得经过节点的所有价值。但每个节点的价值只能被获得一次。问在同一棵树上进行K次游戏 * ，最多能获得多少价值。 * * 思路：首先从叶节点开始记录每个叶子节点到达根节点的权值和，按照权值排序，然后按照这个顺序 * 再按照权值排序，然后在统计叶子节点到达根节点的权值和，不过这次每个节点的值只能取一 * 次，然后再按照权值和排序，在取前k个叶子节点的值 */#include <iostream>#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>#define LL long long#define MAXN 100005using namespace std;struct Node{ int id; LL val; bool operator <(const Node& other) const{ return val>other.val; }}node[MAXN];int t;int n,k;int u,v;LL res;LL val[MAXN];int pos[MAXN];//记录那个定点是哪个vector<int>edge[MAXN];//从根节点开始建树LL dfs1(int u){//第一遍dfs,统计每个节点到根节点的值 if(node[u].val) return node[u].val; LL res=val[u]; for(int i=0;i<edge[u].size();i++){ int v=edge[u][i]; res+=dfs1(v); } node[u].val+=res;}LL dfs2(int u){//第二遍dfs,统计每个节点到根节点的值，每个节点的值只取一次 if(node[pos[u]].val) return 0; node[pos[u]].val=val[u]; for(int i=0;i<edge[u].size();i++){ int v=edge[u][i]; node[pos[u]].val+=dfs2(v); } return node[pos[u]].val;}void init(){ for(int i=0;i<MAXN;i++){ edge[i].clear(); node[i].val=0; } res=0;}int main(){ // freopen("in.txt","r",stdin); scanf("%d",&t); for(int ca=1;ca<=t;ca++){ init(); printf("Case #%d: ",ca); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)//节点的值 scanf("%lld",&val[i]); for(int i=1;i<n;i++){//建边 scanf("%d%d",&u,&v); edge[v].push_back(u); } for(int i=1;i<=n;i++){ node[i].id=i;//节点初始化 pos[i]=i; if(node[i].val==0) dfs1(node[i].id); } sort(node+1,node+n+1);//给节点排序用于贪心 for(int i=1;i<=n;i++){//将节点的值清零 node[i].val=0; pos[node[i].id]=i; } for(int i=1;i<=n;i++){ if(node[i].val==0){ dfs2(node[i].id); } } sort(node+1,node+n+1); for(int i=1;i<=n;i++){ node[i].val=0; pos[node[i].id]=i; } for(int i=1;i<=n&&k;i++){ if(node[i].val==0){ dfs2(node[i].id); k--; res+=node[i].val; } } printf("%lld\n",res); } return 0;}
HDU 5242 Game（三个贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。