简答题
偏难
#22100
day1-3 传统型
day1-3 传统型



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 2010;
vector<int> adj[MAXN];
int pos[MAXN]; // 数字i的初始节点
int ans[MAXN]; // 数字i的最终节点
int parent[MAXN]; // BFS中记录父节点
// 查找从u到v的路径(节点序列,不包含u,包含v)
vector<int> findPath(int u, int v, int n) {
fill(parent, parent + n + 1, -1);
queue<int> q;
q.push(u);
parent[u] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == v) break;
for (int neighbor : adj[cur]) {
if (parent[neighbor] == -1) {
parent[neighbor] = cur;
q.push(neighbor);
}
}
}
vector<int> path;
int cur = v;
while (parent[cur] != 0) {
path.push_back(cur);
cur = parent[cur];
}
reverse(path.begin(), path.end());
return path;
}
// 查找u所在连通块中的最小节点
int findMinNode(int u, int n) {
vector<bool> visited(n + 1, false);
queue<int> q;
q.push(u);
visited[u] = true;
int minNode = u;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur < minNode) minNode = cur;
for (int neighbor : adj[cur]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
return minNode;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> pos[i];
ans[i] = pos[i];
adj[i].clear();
}
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
int u = ans[i];
int minNode = findMinNode(u, n);
if (u == minNode) continue;
vector<int> path = findPath(u, minNode, n);
ans[i] = minNode;
// 移除路径上的边(简化处理,实际需更精确标记)
int prev = u;
for (int v : path) {
auto& vec = adj[prev];
vec.erase(find(vec.begin(), vec.end(), v));
auto& vec2 = adj[v];
vec2.erase(find(vec2.begin(), vec2.end(), prev));
prev = v;
}
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << (i == n ? "\n" : " ");
}
}
return 0;
}</pre><p><br/></p>
解析
方法思路
1、树的表示:使用邻接表表示树的结构。
2、贪心策略:对于每个数字从 1 到 n,找到其当前所在节点所在连通块中编号最小的节点,然后通过路径查找将该数字移动到该最小节点。
3、路径查找:使用广度优先搜索(BFS)查找当前节点到最小节点的路径,并标记路径上的边为已处理,确保后续处理不重复使用这些边。
代码解释
1、输入处理:读取多组测试数据,构建树的邻接表,并记录每个数字的初始节点。
2、查找最小节点:对于每个数字,使用 BFS 查找其所在连通块中编号最小的节点。
3、路径查找:使用 BFS 查找当前节点到最小节点的路径。
4、更新节点与边:将数字移动到最小节点,并移除路径上的边,确保后续处理不重复使用这些边。
5、输出结果:输出每个数字最终所在的节点编号,形成字典序最小的排列。
该方法通过贪心策略和 BFS 路径查找,确保每次将数字移动到最小可能的节点,从而得到字典序最小的结果。