PAT1106(BFS)
2024-09-05 08:41:39
思路
BFS用在tree上,这一个题里主要关注的是用vector去保存每一个节点所连接的子节点,当BFS 时,一旦发现该节点下面没有子节点,这一层一定是最短的路径,然后用当前的层数去为后面的节点做判断,如果接下来,仍然有节点没有子节点,那么用层数去验 证,如果层数一致则是,否则不是。
STL——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 ;
}
最新文章
- CSS书写规范
- 自定义不等高cell—storyBoard或xib自定义不等高cell
- Kali Linux Web 渗透测试视频教程— 第十三课-密码破解
- Multiple MySQL running but PID file could not be found
- 静态库不要strip 太厉害
- Java调优之jvm和线程的内存分析
- javaweb之Filter详解(转)
- 最详细的JavaScript和事件解读
- Linux malloc大内存的方法
- 纯CSS实现tab选项卡切换
- 【转】人工智能(AI)资料大全
- Python爬虫 URLError异常处理
- 利用layer实现MVC页面数据互交提示弹框
- 深入 JAVA里面关于byte数组和String之间的转换问题
- 从零单排学Redis【黄金】
- js复习--基础
- Oracle 11g透明网关连接Sqlserver
- 学习Tensorflow的LSTM的RNN例子
- luogu 3790 文艺数学题 - 矩阵树定理 - 容斥原理
- 每天一个小程序—0013题(爬图片+正则表达式 or BeautifulSoup)