今天莫名其妙负能量爆发惹,还好还有两天就去听GIN🎸的live了……日推的歌还一首比一首远离人世……………没办法集中精神的丧啊…………莫非脑缺氧……刚买的运动耳机,晚上跑步好了 = =
我活了,跟女🦢对骂有奇效嗷,我很满意
分析两道值得仔细磨一磨的题吧 = =
- 求🌲的直径(树上的最长链)
- 树的遍历➕回溯(保存路径),并对路径排序。
1053 Path of Equal Weight (30 分)
- ⚠️对等权重路径的排序:不必,在建树时,排序,可以保证先遍历到符合题意的较大
- ⚠️剪枝:如果当前路径上点权之和已经大于total,直接返回
-
⚠️path的维护:两种方式。
- 使用vector,及时push_back,pop_back
- 使用数组记录,要在DFS中添加一个参数记录数组中元素个数,以便覆盖、加入新结点。
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int weight[100] = {0};
vector<int> nodes[100], path;
int nn, mm, total;
bool cmp(const int n1, const int n2) {
return weight[n1] > weight[n2];
}
void DFS(int root, int temp) {
if (temp > total) return;
if (temp == total && nodes[root].empty()) {
int len = path.size() - 1;
for (int i = 0; i < len; i++) {
printf("%d ", weight[path[i]]);
}
printf("%d\n", weight[path.back()]);
}
for (auto item:nodes[root]) {
path.emplace_back(item);
DFS(item, temp + weight[item]);
path.pop_back();
}
}
int main() {
scanf("%d%d%d", &nn, &mm, &total);
for (int i = 0; i < nn; ++i) {
scanf("%d", &weight[i]);
}
for (int i = 0; i < mm; ++i) {
int father, cnt, son;
scanf("%d%d", &father, &cnt);
for (int j = 0; j < cnt; ++j) {
scanf("%d", &son);
nodes[father].emplace_back(son);
}
sort(nodes[father].begin(), nodes[father].end(), cmp);
}
path.emplace_back(0);
DFS(0, weight[0]);
return 0;
}
1021 Deepest Root (25 分)
若图连通、且恰有N — 1 条边,则能确定是一棵树。
(以下找 root 的策略来自「算法笔记」,证明十分精彩!!!这里没有放上来)
下面的任务就是选择合适的根结点,使得树的高度最大。具体做法为:
- 先任意选择一个结点,从该结点开始遍历整棵树,获取能达到的最深的顶点(记为结点集合 A);
- 然后从集合 A 中任意个结点出发遍历整棵树,获取能达到的最深的顶点(记为结点集合 B)。这样集合 A 与集合 B 的并集即为所求的使树高最大的根结点。
实现
- 算法笔记的解法
并查集求连通分量、若连通分量仅有1个(是🌲),两次DFS求树的直径。
⚠️记录前驱防止无向图无限循环出不来。(若孩子为前驱则continue) - 下面是我的写法,visited数组记录结点是否已经访问过,BFS求连通分量数,若一次BFS就访问了所有结点,则是🌲,再次初始化visited数组,max_level,再一次BFS……;否则,访问全部结点所需BFS次数即连通分量数。
⚠️一定要注意visited数组的更新、重置
⚠️用迭代器取集合元素:✳️ (*set1.begin()
)
⚠️合并集合写法:set1.insert(set2.begin(), set2.end());
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
using namespace std;
bool visited[10001] = {false};
int levels[10001] = {0}, max_level = 0;
vector<int> nodes[10001];
set<int> roots;
int nn;
void BFS(int root) {
queue<int> mq;
mq.push(root);
while (!mq.empty()) {
int curr = mq.front();
mq.pop();
visited[curr] = true;
for (auto item:nodes[curr]) {
if (visited[item]) continue; // 无环无向图 防止无穷loop
mq.push(item);
levels[item] = levels[curr] + 1;
if (levels[item] > max_level) {
max_level = levels[item];
roots.clear();
}
roots.insert(item);
}
}
}
int main() {
scanf("%d", &nn);
if (nn == 1) {
puts("1");
return 0;
}
for (int i = 1; i < nn; ++i) {
int father, son;
scanf("%d%d", &father, &son);
nodes[father].emplace_back(son); //无向图
nodes[son].emplace_back(father);
}
int cnt_cc = 0;
levels[1] = 1;
for (int i = 1; i <= nn; ++i) {
if (!visited[i]) {
BFS(i);
cnt_cc++;
}
}
if (cnt_cc == 1) {
set<int> res = roots;
int new_st = *roots.begin();
roots.clear();
fill(visited + 1, visited + nn + 1, false);
BFS(new_st);
res.insert(roots.begin(), roots.end());
for (auto item:res) {
printf("%d\n", item);
}
} else printf("Error: %d components\n", cnt_cc);
return 0;
}
网友评论