L2-020. 功夫传人
一门武功能否传承久远并被发扬光大,是要看缘分的。一般来说,师傅传授给徒弟的武功总要打个折扣,于是越往后传,弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子(或者是吃到了灵丹、挖到了特别的秘笈),会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。
这里我们来考察某一位祖师爷门下的徒子徒孙家谱:假设家谱中的每个人只有1位师傅(除了祖师爷没有师傅);每位师傅可以带很多徒弟;并且假设辈分严格有序,即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z,每向下传承一代,就会减弱r%,除非某一代弟子得道。现给出师门谱系关系,要求你算出所有得道者的功力总值。
输入格式:
输入在第一行给出3个正整数,分别是:N(<=105)——整个师门的总人数(于是每个人从0到N-1编号,祖师爷的编号为0);Z——祖师爷的功力值(不一定是整数,但起码是正数);r ——每传一代功夫所打的折扣百分比值(不超过100的正数)。接下来有N行,第i行(i=0, ..., N-1)描述编号为i的人所传的徒弟,格式为:
Ki ID[1] ID[2] ... ID[Ki]
其中Ki是徒弟的个数,后面跟的是各位徒弟的编号,数字间以空格间隔。Ki为零表示这是一位得道者,这时后面跟的一个数字表示其武功被放大的倍数。
输出格式:
在一行中输出所有得道者的功力总值,只保留其整数部分。题目保证输入和正确的输出都不超过1010。
输入样例:10 18.0 1.00 3 2 3 5 1 9 1 4 1 7 0 7 2 6 1 1 8 0 9 0 4 0 3输出样例:
404
思路:BFS
将祖师爷加入队列,然后遍历它的ans数组,将徒儿加入队列,依次类推计算每个人的功力。
反思:当时写的时候用的并查集,然后写的还挺乱的,包括0后面的数字意义理解错了。
再次写的时候用到了队列,然后重新理解了题意。但是还是坑了一下,刚开始没用保存徒儿编号的方法,而是一次次遍历,超时。
然后最后只计算得道者的功力和,要看仔细,这个地方耗了不少时间。
代码:
#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<vector> #include<string> #include<algorithm> #include<cmath> using namespace std; const int maxn=1e5+5; struct node { int x,id;//x放大的倍数,id自身的编号 double force;//自身的功力 vector<int> ans;//保存徒儿的下标 node() { x=0; force=0; id=0; } }; node per[maxn]; void bfs(int n, double r) { queue<node> q; node t1=per[0]; q.push(t1); double sum=0; while(!q.empty()) { t1=q.front(); q.pop(); if(t1.x) sum+=t1.force; int len=t1.ans.size(); for(int i=0;i<len;++i) { per[t1.ans[i]].force=t1.force*r; if(per[t1.ans[i]].x) { per[t1.ans[i]].force*=per[t1.ans[i]].x; } node t2=per[t1.ans[i]]; q.push(t2); } } printf("%d ",(int)sum); } int main() { int n; double z,r; scanf("%d %lf %lf",&n,&z,&r); per[0].force=z; r=(1.0-r/100.0); for(int i=0;i<n;++i) { per[i].id=i; int k;scanf("%d",&k); if(!k) { scanf("%d",&per[i].x);continue; } int stuid; for(int j=0;j<k;++j) { scanf("%d",&stuid); per[i].ans.push_back(stuid); } } if(per[0].x) per[0].force*=per[0].x;//特判祖师爷也是得道者的情况 bfs(n,r); return 0; }