AcWing 5074. 机场登机口调整模拟
原题链接
中等
bfs + 模拟
收获:
- 自定义
sort
函数
- 复习了
bfs
的模板
memset
的使用,记得一定要初始化为-1
- 理解怎样获取输出前的编号和输出后的编号(对p数组进行排序)
- 还有就是收获了数据的输入方面的写法
- 用二维数组维护父子关系
while(scanf("%d%d", &num, &flow) != -1)
的使用,针对的是不知道有多少个数据输入的情况(本题是不知道有多少个叶子节点)
本题还总结出一个模板(针对bfs):对数组排序,并返回原来的编号和排序后的编号(用权重进行排序)
- 需要有一个
p
数组用来记录编号
- 然后用
p
数组进行sort
- p[]对应的是之前的编号,取出来的那个元素对应的是之后的位置(编号)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
// 定义树的结构
int tr[N][3]; // 存储树的结构
int w[N]; // 存储登机口的流量
int p[N]; // 存储登机口编号
int cnt; // 登机口数量
// 广度优先搜索遍历树的每个节点并输出
void bfs() {
queue<int> q;
q.push(100);
int k = 0;
while (!q.empty()) {
auto t = q.front();
q.pop();
if (t < 100) // 如果当前节点编号小于100,说明是叶子节点(即登机口)
printf("%d %d\n", p[k++], t);
else { // 否则是分叉结点
for (int i = 0; i < 3; i++) {
int j = tr[t][i];
if (j != -1) // 子节点存在则入队
q.push(j);
}
}
}
}
int main() {
// 输入树结构
scanf("%d", &n);
memset(tr, -1, sizeof tr);
for (int i = 0; i < n; i++) {
int t;
scanf("%d", &t);
for (int j = 0; j < 3; j++)
scanf("%d", &tr[t][j]);
}
// 输入登机口流量
int num, flow;
while (scanf("%d%d", &num, &flow) != EOF) {
w[num] = flow;
p[cnt++] = num;
}
// 根据流量排序登机口,流量大的在前,流量相同的按照编号升序排列
sort(p, p + cnt, [&](int a, int b) {
if (w[a] != w[b]) return w[a] > w[b];
return a < b;
});
// 输出调整结果
bfs();
return 0;
}