树删边操作求字典序最小排列的C++实现

### 🌟思路分析 本题的核心目标是通过合理安排删边操作，使得按数字从小到大顺序，数字 `1` 到 `n` 所在的结点编号排列的字典序最小。可以使用深度优先搜索（DFS）结合回溯的方法来尝试所有可能的删边顺序，找到最优方案。 ### 💻代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; const int MAXN = 2005; int T, n; int num[MAXN]; // 存储数字 i 初始所在的结点编号 vector<int> edges[MAXN]; // 存储树的边 vector<pair<int, int>> allEdges; // 存储所有边 vector<int> ans; // 存储最终答案 // 生成所有可能的删边顺序 void dfs(int step, vector<int> order, vector<int> currentNum) { if (step == n - 1) { vector<int> result(n + 1); for (int i = 1; i <= n; i++) { result[currentNum[i]] = i; } vector<int> currentAns; for (int i = 1; i <= n; i++) { currentAns.push_back(result[i]); } if (ans.empty() || currentAns < ans) { ans = currentAns; } return; } for (int i = 0; i < allEdges.size(); i++) { if (find(order.begin(), order.end(), i) == order.end()) { vector<int> newOrder = order; newOrder.push_back(i); vector<int> newNum = currentNum; int u = allEdges[i].first, v = allEdges[i].second; // 交换两个结点上的数字 for (int j = 1; j <= n; j++) { if (newNum[j] == u) newNum[j] = v; else if (newNum[j] == v) newNum[j] = u; } dfs(step + 1, newOrder, newNum); } } } int main() { cin >> T; while (T--) { cin >> n; for (int i = 1; i <= n; i++) { cin >> num[i]; } for (int i = 1; i <= n; i++) { edges[i].clear(); } allEdges.clear(); ans.clear(); for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; edges[x].push_back(y); edges[y].push_back(x); allEdges.emplace_back(x, y); } vector<int> order; dfs(0, order, vector<int>(num + 1, num + n + 1)); for (int i = 0; i < n; i++) { if (i > 0) cout << " "; cout << ans[i]; } cout << endl; } return 0; } ``` ### 代码解释 1. **输入处理**：首先读取测试数据的组数 `T`，对于每组数据，读取树的大小 `n`、每个数字初始所在的结点编号，以及树的边信息。 2. **深度优先搜索**：`dfs` 函数用于生成所有可能的删边顺序。在每次递归中，尝试选择一条未被选择的边进行删除，并交换该边连接的两个结点上的数字，然后继续递归。 3. **记录最优结果**：当完成 `n - 1` 次删边操作后，根据当前数字所在的结点编号生成排列，并与之前记录的最优排列比较，更新最优排列。 4. **输出结果**：对于每组测试数据，输出最优方案下的结点编号排列。 ### 复杂度分析 - **时间复杂度**：由于需要尝试所有可能的删边顺序，时间复杂度为 $O((n - 1)!)$。 - **空间复杂度**：主要用于存储树的边和递归栈，空间复杂度为 $O(n)$。 ######[AI问答 | 1007点数解答 | 2026-05-30 20:42:22]