打卡信奥刷题（2529）用C++实现信奥 P2018 消息传递

P2018 消息传递

题目描述

巴蜀国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果AAA是BBB的上级，BBB是CCC的上级，那么AAA就是CCC的上级。绝对不会出现这样的关系：AAA是BBB的上级，BBB也是AAA的上级。

最开始的时刻是000，你要做的就是用111单位的时间把一个消息告诉某一个人，让他们自行散布消息。在任意一个时间单位中，任何一个已经接到消息的人，都可以把消息告诉他的一个直接上级或者直接下属。

现在，你想知道：

1. 到底需要多长时间，消息才能传遍整个巴蜀国的所有人？
2. 要使消息在传递过程中消耗的时间最短，可供选择的人有那些？

输入格式

输入文件的第一行为一个整数NNN（N≤1000N\le 1000N≤1000），表示巴蜀国人的总数，假如人按照111到nnn编上了号码，国王的编号是111。第222行到第NNN行（共N−1N-1N−1行），每一行一个整数，第iii行的整数表示编号为iii的人直接上级的编号。

输出格式

文件输出共计两行：

• 第一行为一个整数，表示最后一个人接到消息的最早时间。
• 第二行有若干个数，表示可供选择人的编号，按照编号从小到大的顺序输出，中间用空格分开。

输入输出样例 #1

输入 #1

8 1 1 3 4 4 4 3

输出 #1

5 3 4 5 6 7

C++实现

#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;intcnt,n,anst=0x7fffffff,f[1005],ans[1005],h[2005];boolv[1005];structedge{intn,t;}e[2005];//前向星voidadd(intx,inty){e[++cnt].t=y;e[cnt].n=h[x];h[x]=cnt;}voiddp(intx){intd[1005]={0},y;v[x]=1;//标记x已访问for(inti=h[x];i;i=e[i].n){y=e[i].t;if(!v[y]){dp(y);//计算子结点d[++d[0]]=f[y];}}sort(d+1,d+d[0]+1);for(inti=1;i<=d[0];i++)f[x]=max(f[x],d[i]+d[0]-i+1);}intmain(){cin>>n;for(inti=2;i<=n;i++){intx;cin>>x;add(i,x);add(x,i);}for(inti=1;i<=n;i++){memset(f,0,sizeof(f));memset(v,0,sizeof(v));//每次枚举初始化dp(i);if(anst>f[i]){anst=f[i];ans[0]=0;ans[++ans[0]]=i;}elseif(anst==f[i])ans[++ans[0]]=i;//更新最快传播时间并记录根结点}cout<<anst+1<<endl;//答案要加1for(inti=1;i<=ans[0];i++)cout<<ans[i]<<" ";return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容