2019 树上的数 · 方案一全排列暴力

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1967 字

n 个点的树，每点一个 1..n 的数字

2019
树

正文

// CSP-S 2019 复赛 T3 · 树上的数（方案一：全排列暴力，n ≤ 10 部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2019C
// 题意：n 个点的树，每点一个 1..n 的数字。每次操作选一条未删的边，
//       交换这条边两个端点上的数字，然后删掉它。n-1 次后按数字
//       1..n 所在结点编号写出排列 P，求字典序最小的 P。
// 思路（全排列模拟）：
//   n ≤ 10 时删边顺序只有 (n-1)! 种，逐个枚举：
//   - 每种顺序依次模拟：交换边两端数字 → 标记边已删；
//   - 模拟完读出 pos[d] = 数字 d 所在点，组成排列 P；
//   - 与当前最优比较取字典序更小者。
//   T ≤ 10、7! = 5040 种顺序，每组总计算量 ~4e5，轻松通过
//   测试点 1~2；更大的 n 交给方案二。
// 复杂度：O(T · (n-1)! · n)。
// 易错点：
//   1. 多组数据每次重置数字位置与边的删除标记；
//   2. 排列比较直接逐位比（数字位数相同，字典序 = 数值序逐位比）；
//   3. next_permutation 的序列要先有序（用 1..n-1 初始化）。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int T, n;
int eu[12], ev[12], order[12];
int pos[12], best[12], tmp[12];

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int d = 1; d <= n; d++) scanf("%d", &pos[d]);
        for (int i = 1; i < n; i++) {
            scanf("%d%d", &eu[i], &ev[i]);
            order[i] = i;
        }
        bool first = true;
        do {
            int cur[12];
            for (int d = 1; d <= n; d++) cur[d] = pos[d];
            for (int k = 1; k < n; k++) {
                int e = order[k];
                swap(cur[eu[e]], cur[ev[e]]);
            }
            // 读出排列：数字 d 所在点
            int where[12];
            for (int v = 1; v <= n; v++) where[cur[v]] = v;
            for (int d = 1; d <= n; d++) tmp[d] = where[d];
            bool better = first;
            if (!better)
                for (int d = 1; d <= n; d++)
                    if (tmp[d] != best[d]) { better = tmp[d] < best[d]; break; }
            if (better) {
                first = false;
                for (int d = 1; d <= n; d++) best[d] = tmp[d];
            }
        } while (next_permutation(order + 1, order + n));
        for (int d = 1; d <= n; d++) printf("%d%c", best[d], d == n ? '\n' : ' ');
    }
    return 0;
}

2019 树上的数 · 方案一 全排列暴力

正文

CSP-S 标程 · 复赛真题的其它内容

2019 树上的数 · 方案一全排列暴力