P5183 [COCI 2009] POSLOZI

伟大的王夫子 · 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]);
    }
}