题目描述
一棵树上每个节点有一个编号和一个数,每次删除树上的一条边,同时交换节点上的数,删完所有边后把节点上的数从小到大排,求这些数所在的节点编号形成的数列的最小字典序。
算法
(暴力枚举)
这里仅介绍暴力部分分做法。事实上,这题是一道难度很大的题了,部分分也不是很好获得。
暴力的部分还是很简单的,直接生成 $1 \sim n-1$ 的全排列,然后按排列的顺序删边,对于每次操作完得到的结果,保留字典序最小的即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using std::cin;
using std::cout;
const int MX = 2005;
int a[MX], p[MX], ans[MX]; // 分别表示节点上的数,数对应的节点,答案
int g[MX][2]; // 存下每条边,便于删除
int b[MX], q[MX], d[MX];
void solve() {
int n;
cin >> n;
rep(i, n) {
cin >> p[i];
a[p[i]] = i;
}
for (int i = 1; i < n; ++i) cin >> g[i][0] >> g[i][1];
for (int i = 1; i < n; ++i) d[i] = i;
ans[1] = 1e9;
do {
rep(i, n) { // 每一次都要从初始状态出发
b[i] = a[i];
q[i] = p[i];
}
for (int i = 1; i < n; ++i) { // 两个都要交换
std::swap(b[g[d[i]][0]], b[g[d[i]][1]]);
std::swap(q[b[g[d[i]][0]]], q[b[g[d[i]][1]]]);
}
rep(i, n) { // 判断字典序是否更小
if (q[i] < ans[i]) {
for (int j = i; j <= n; ++j) ans[j] = q[j];
break;
}
else if (q[i] > ans[i]) break;
}
} while (std::next_permutation(d+1, d+n));
rep(i, n) cout << ans[i] << " \n"[i == n];
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int t;
cin >> t;
while (t--) solve();
return 0;
}