PAT 1106

思路

BFS用在tree上,这一个题里主要关注的是用vector去保存每一个节点所连接的子节点,当BFS 时,一旦发现该节点下面没有子节点,这一层一定是最短的路径,然后用当前的层数去为后面的节点做判断,如果接下来,仍然有节点没有子节点,那么用层数去验 证,如果层数一致则是,否则不是。

STL——vector

vector

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define LL long long;
using namespace std;
const int MAXN=;
double pi,r;
struct node//节点
{
int v;//节点编号
int cnt;//记录距离根节点的层数
};
vector <int> p[MAXN];//构造这棵树
queue <node> q;
int minct=-;
int bfs()
{
int c=;
bool flag = false; while(!q.empty())
{
node nd = q.front();
q.pop();
int id = nd.v;
int ct = nd.cnt;
//初始情况下flag记为false,也就是还未有叶子节点
//当第一次出现有叶子节点是flag变为true
//如果flag记为true,那么后面的节点如果还有子节点也没有必要再放进去了
if(p[id].size()!=)
{
if(flag==false)
{
int len = p[id].size();
for(int i = ;i<len;i++)
{
node tn={p[id][i],ct+};//结构体对象赋值的简化表达
q.push(tn);
}
}
}
else
{
//如果第一次有叶子节点即(flag==false)
//或者后面发现叶子节点层数相同(minct==ct)
if(flag==false||minct==ct)
{
flag=true;
minct=ct;
c++;
}
}
}
return c;
}
int main()
{
freopen("1106.txt","r",stdin);
int m,k,t,s;
cin>>m>>pi>>r;
for(int i = ;i<m;i++)
{
scanf("%d",&k);
for(int j = ;j<=k;j++)
{
scanf("%d",&t);
p[i].push_back(t);
}
}
node nd;
nd.v=;
nd.cnt=;
q.push(nd);
s = bfs();
for(int i = ;i<=minct;i++)
{
pi=pi*(+r/100.0);
}
printf("%.4lf %d\n",pi,s);
return ;
}

最新文章

  1. CSS书写规范
  2. 自定义不等高cell—storyBoard或xib自定义不等高cell
  3. Kali Linux Web 渗透测试视频教程— 第十三课-密码破解
  4. Multiple MySQL running but PID file could not be found
  5. 静态库不要strip 太厉害
  6. Java调优之jvm和线程的内存分析
  7. javaweb之Filter详解(转)
  8. 最详细的JavaScript和事件解读
  9. Linux malloc大内存的方法
  10. 纯CSS实现tab选项卡切换
  11. 【转】人工智能(AI)资料大全
  12. Python爬虫 URLError异常处理
  13. 利用layer实现MVC页面数据互交提示弹框
  14. 深入 JAVA里面关于byte数组和String之间的转换问题
  15. 从零单排学Redis【黄金】
  16. js复习--基础
  17. Oracle 11g透明网关连接Sqlserver
  18. 学习Tensorflow的LSTM的RNN例子
  19. luogu 3790 文艺数学题 - 矩阵树定理 - 容斥原理
  20. 每天一个小程序—0013题(爬图片+正则表达式 or BeautifulSoup)

热门文章

  1. 【python】-- RabbitMQ RPC模型
  2. 我的Android进阶之旅------>Android KeyCode列表
  3. react create app ,nginx服务器配置
  4. PhpStorm编辑器
  5. 小程序网络请求arraybuffer 转为base64
  6. python3.7.1 内置函数
  7. Vue-Quill-Editor回显不显示空格的处理办法
  8. RabbitMQ事务确认机制(生产者)
  9. Hadoop- 集群启动详解
  10. Sobel边缘检测