using namespace std;
#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
//#include<string>
//#include<iostream>
//#include<utility>
//#include<algorithm>
#define REG
#define INL
#define MAX(x, y) (x < y ? y : x)
#define MIN(x, y) (x < y ? x : y)
#define ABS(x) (x < 0 ? -x : x)
#define N 1000
#define LL long long
#define INF 1145141919
#define EPS 0.00001
template <typename T>
INL T Max(REG T x, REG T y) {
    return MAX(x, y);
}
template <typename T>
INL T Min(REG T x, REG T y) {
    return MIN(x, y);
}
template <typename T>
INL T Abs(REG T x) {
    return ABS(x);
}
template <typename T>
INL void Swap(REG T &x, REG T &y) {
    x ^= y ^= x ^= y;
}
template <typename T>
INL void Gcd(REG T x, REG T y) {
    while (y ^= x ^= y ^= x %= y)
        ;

    return x;
}
template <typename T>
INL void read(REG T &x) {
    x = 0;
    REG char c = getchar(); /*REG T fl=1;*/

    while (c < '0' || c > '9') { /*if(c == '-')fl=-1;*/
        c = getchar();
    }

    while ('/' < c && c < ':') {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    } /*x*=fl;*/
}
int n, m;
int swp[N][N];
int vis[N];
int c(int *a) {
    int cnt = 0;

    for (int i = 1; i <= n; i++)
        if (a[i] != i)
            cnt += (swp[i][a[i]] ? 1 : 2);

    return cnt;
}
struct st {
    int a[N], stp;

    bool operator<(const st &oth) const {
        for (int i = 1; i <= n; i++)
            if (a[i] != oth.a[i])
                return a[i] < oth.a[i];

        return 0;
    }
    //  */
    int cxk() {
        for (int i = 1; i <= n; i++)
            if (a[i] != i)
                return 0;

        return 1;
    }
};
struct st2 {
    int a[N], stp;
    bool operator()(st x, st y) {
        return x.stp + c(x.a) > y.stp + c(y.a);
    }
};
st s;
priority_queue<st, vector<st>, st2> q;
map<st, int> com;
void bfs() {
    q.push(s);
    com[s] = 0;

    while (!q.empty()) {
        st u = q.top();
        q.pop();

        if (u.cxk())
            return;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                st v = u;
                v.stp++;

                if (swp[i][j]) {
                    Swap(v.a[i], v.a[j]);

                    if (com.find(v) != com.end())
                        continue;

                    com[v] = swp[i][j];
                    q.push(v);
                }
            }
        }
    }
}
int cx[N], cy[N];
void d(st k, int cnt) {
    if (com[k] == 0) {
        printf("%d\n", cnt);
        return;
    } //xxrxxr

    int id = com[k];
    Swap(k.a[cx[id]], k.a[cy[id]]); //xxrxxrxxrxxr
    d(k, cnt + 1);
    printf("%d\n", id);
}
st e;
int main() {
    read(n);
    read(m);

    for (int i = 1; i <= n; i++)
        read(s.a[i]);

    for (int i = 1; i <= m; i++) {
        read(cx[i]);
        read(cy[i]);
        swp[cx[i]][cy[i]] = swp[cy[i]][cx[i]] = i;
    }

    for (int i = 1; i <= n; i++)
        e.a[i] = i;

    bfs();
    d(e, 0);
    return 0;
}

题解

问题分析

本题要求将一个长度为 $N$ 的排列通过给定的 $M$ 种交换操作（每次可选择一种操作交换指定位置的元素）转换为升序排列 $1, 2, \ldots, N$，需找到修改次数最少的方案。

• 输入：排列长度 $N$、操作数 $M$、初始排列、$M$ 种交换操作（每种操作对应一对位置 $L, R$）。
• 输出：最少操作次数及具体操作序列。

算法选择

由于 $N \leq 12$，排列的可能状态数为 $12! = 479001600$，直接暴力枚举所有状态效率较低。因此采用 A 算法*（启发式搜索），结合优先级队列优化搜索过程，同时使用哈希表记录已访问状态以避免重复计算。

• A 算法*：通过启发函数估计当前状态到目标状态的距离，优先扩展更可能接近目标的状态，提高搜索效率。
• 启发函数设计：对于当前排列，统计每个元素与目标位置的偏差，若可直接交换则计 $1$ 次，否则计 $2$ 次，估计最少操作次数。

代码解析

1. 数据结构

• struct st：存储当前排列状态及已执行的操作次数。
• 优先级队列 priority_queue：基于状态的估计总代价（当前操作数 + 启发函数值）排序，优先扩展代价小的状态。
• 哈希表 map<st, int>：记录每个状态对应的上一步操作，用于回溯操作序列。

2. 核心步骤

1. 初始化：读取输入，初始化初始状态和目标状态（升序排列 $1, 2, \ldots, N$）。
2. A 搜索*：从初始状态出发，对每种允许的交换操作生成新状态，计算代价并加入队列，直至找到目标状态。
3. 回溯路径：通过哈希表记录的操作反向追溯，输出最少操作次数及具体操作序列。

3. 关键函数

• c(int *a)：计算启发函数值，估计当前状态到目标的最少操作次数。
• bfs()：实现 A* 搜索过程，扩展状态并记录路径。
• d(st k, int cnt)：回溯并输出操作序列。

算法标签

• 启发式搜索（A* 算法）
• 状态压缩
• 回溯法
• 哈希表

复杂度分析

• 时间复杂度：取决于状态空间大小和启发函数的优化效果，最坏情况下为 $O(12! \times M)$，但实际通过 A* 算法可大幅减少搜索状态。
• 空间复杂度：$O(12!)$，用于存储访问过的状态。

该方法高效利用启发式信息引导搜索方向，在 $N \leq 12$ 的约束下能快速找到最优解。