自动搬运

查看原文

来自洛谷，原作者为

	伟大的王夫子 hanser忠实粉丝，爱好ACG、古风

搬运于2025-08-24 22:07:59，当前版本为作者最后更新于2021-10-28 15:40:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先看数据范围 $n \le 12$，就差告诉我们就是一道搜索题了。否则，为什么不把数据范围扩大？

首先，个人认为这题广搜应该不太行。毕竟一个队列中的节点还需要记录许多信息，对于我而言，我认为十分麻烦。不过听说本题可以用 A* 过。 下面我介绍一种比较方便的方法 IDA*。

搜索算法的本身框架十分简单，这里便不多说了。主要讨论搜索的优化

剪枝一：不妨设刚刚使用的操作编号为 $i$，那么这一次搜索一定不能使用该操作。虽然这个剪枝可能优化效果不好，但是乱剪枝总比不剪好。

剪枝二：估价函数。我们不妨设当前排列与全排列对不上的个数为 $cnt$，那么估价函数明显可以设置为$\lceil{\dfrac{cnt}{2}} \rceil$。可惜的是，这个剪枝仍然不够强。那我们再进一步优化。我们设当前排列为 $a$，$d_{i,j}$ 为第 $i$ 个位置上的数与第 $j$ 个位置上的数交换位置最少需要的次数。其中，$d$ 数组可以提前用 floyd 算法求出。此时，我们便可以设 $\lceil \dfrac{\sum_{i = 1}^n d_{i,a_i}}{2} \rceil$ 为我们的估价函数。这个剪枝的效果相当之好。 也是 IDA* 的精华所在。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[13], b[170][2], depth, d[13][13];
vector<int> p, _p;
int h() {
	int cnt = 0;
	for (register int i = 1; i <= n; ++i) cnt += d[i][a[i]];
	return cnt;
}
bool dfs(int dep, int pre) {
	int k = h();
	if (!k) {
	   _p = p;
	   return 1;
	}
	if (2 * dep + k > 2 * depth) return 0;
	for (register int i = 1; i <= m; ++i)
		if (pre != i) {
			swap(a[b[i][0]], a[b[i][1]]);
			p.push_back(i);
			if (dfs(dep + 1, i)) return 1;
			p.pop_back();
			swap(a[b[i][0]], a[b[i][1]]);	
		}
	return 0;
}
int main() {
	scanf("%d%d", &n, &m);
	memset(d, 0x3f, sizeof d);
	for (register int i = 1; i <= n; ++i) scanf("%d", a + i), d[i][i] = 0;
	for (register int i = 1; i <= m; ++i) {
		scanf("%d%d", b[i], b[i] + 1);
		d[b[i][0]][b[i][1]] = d[b[i][1]][b[i][0]] = min(d[b[i][1]][b[i][0]], 1);
	}
	for (register int k = 1; k <= n; ++k)
		for (register int i = 1; i <= n; ++i)
			for (register int j = 1; j <= n; ++j)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	depth = 0;
	while (!dfs(0, -1) && depth <= 30) ++depth;
	if (depth == 31) puts("NEMA");
	else {
		printf("%d\n", depth);
		for (register int i = 0; i < _p.size(); ++i) printf("%d\n", _p[i]);
	}
}