本文主要是介绍小火山 zzuli 1907 (宝藏),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
小火山的宝藏收益
Description
进去宝藏后, 小火山发现宝藏有N个房间,且这n个房间通过N-1道门联通。
每一个房间都有一个价值为Ai的宝藏, 但是每一个房间也都存在一个机关。如果小火山取走了这个房间的宝藏,那么这个房间通往其他房间的门就永远打不开了,也就是说后面的宝藏小火山是得不到了(进入这个房间的门是不会关闭的,小火山还是可以回去的);如果小火山不取这个宝藏,而是去打开通往另一房间的门,那么这个房间的宝藏就会消失, 小火山就得不到这个房间的宝藏。
不过,小火山已经有了藏宝图,知道每一个房间的宝藏的价值,现在想请你帮小火山算一下,他最多能获得多少钱去买股票?
Input
输入第一行是一个整数T(T <= 50), 表示一共有T组数据。
对于每一组数据,第一行是两个数N, S(1 <= N <= 10000, 1 <= S <= N), N代表有N个房间, S代表小火山进去宝藏后的
起始房间(小火山怎么进入起始房间不重要),第二行是N个数,代表每个房间宝藏的价值, 随后N-1行, 每行两个数A, B, 代表
A, B这两个房间联通。
Output
对于每一组数据输出一个整数, 代表小火山能获得的最大钱数。
Sample Input
2 1 1 20 3 1 4 5 6 1 2 2 3
Sample Output
20 6
题解:dfs+邻接表,其实相当于一棵树,到每个节点有两种选择,停在该节点或继续往下走,比较该节点的价值与其余子节点的价值即可。(邻接表不太熟悉,想到了dfs,没想到怎么邻接表加边)类似于太子那道题,还没补
#include<cstdio>
#include<cstring>
using namespace std;int n,s;
int w[10005];struct node{int u,v,next;
}edge[10005*2],e;
int edgenum;
int head[10005*2],vis[10005];void init(){edgenum=0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));
}
void add(int a,int b){e={a,b,head[a]};edge[edgenum]=e;head[a]=edgenum++;
}int dfs(int f){int i;vis[f]=1;int sum=0;int maxi=w[f];int num=0;for (i=head[f];i!=-1;i=edge[i].next){int vi=edge[i].v;if (!vis[vi]){sum+=dfs(vi);num++;vis[vi]=1;}} return sum>maxi?sum:maxi;
}
int main(){int t,i;int a,b;scanf ("%d",&t);while (t--){scanf ("%d %d",&n,&s);init();for (i=1;i<=n;i++){scanf ("%d",&w[i]);}for (i=0;i<n-1;i++){scanf ("%d %d",&a,&b);add(a,b);add(b,a);}int ans=dfs(s);printf ("%d\n",ans);}return 0;
}
这篇关于小火山 zzuli 1907 (宝藏)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!