把权值换成序号后每结点 4 位压成 64 位状态,在 M 种交换构成的排列图上 BFS,首次生成合法大根堆排列的层数即最少交换次数。
OJ: roj
题目 ID: 1689
难度:提高
标签:搜索BFS状态压缩位运算python
创建: 2026-10-07 15:54
更新: 2026-10-07 15:54
形式化题目
给定一棵
要求用最少的操作次数,把点权的分布变成一棵大根堆:对每个非根结点
求最少操作次数。数据保证有解。
把"点权的分布"看成一个排列,题目就变成一句纯图论的话:
- 状态:把权值分配到各结点的方案,共
种可能; - 边:每一种交换方式
都是一次"交换排列第 、 个位置",边权为 ; - 起点:题面给定的初始分布;
- 终点集合:所有满足大根堆性质的分布(不止一个);
- 答案:起点到终点集合的最短距离。
正解
思路
第一步:点数权没有意义,只有相对大小有意义。
大根堆的所有条件都是形如"
这一步之后,初始状态
第二步:目标状态不唯一,所以不能"算距离到某一个目标"。
如果题目像八数码那样有唯一目标排列,就可以直接判定可达性;但大根堆只规定了父子间的偏序,
同一棵树上合法的堆排列有很多个。比如
第三步:状态压缩成 64 位整数。
一次交换
a = (state >> su) & 15; // u 的序号
b = (state >> sv) & 15; // v 的序号
state' = state & ~(15 << su) & ~(15 << sv) | (b << su) | (a << sv);判堆也不需要对每个结点单独查表,只需扫一遍
第四步:为什么 BFS 就是答案。
每次交换的代价都是
下面是第一组样例的状态图前三层。权值
flowchart TD S["(3,2,1,0) 起点 d=0"] -->|"(1,2)"| A1["(2,3,1,0)"] S -->|"(1,4)"| A2["(0,2,1,3)"] S -->|"(2,3)"| A3["(3,1,2,0)"] S -->|"(1,3)"| A4["(1,2,3,0)"] A2 -->|"(2,3)"| G["(0,1,2,3) 合法堆 d=2"] A3 -->|"(1,4)"| G A1 -.->|"d=1 层全都不满足堆性质"| X["..."] A4 -.-> X
第 1 层(
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:36
# update_at: 2026-10-07 15:54
import sys
from collections import deque
from collections.abc import Iterator
# 状态编码:state[i] 是结点 i+1 当前持有的权值序号。权值越大序号越小(最大权值为 0),
# 于是「父亲的序号小于儿子的序号」就是大根堆性质,和权值的具体数值无关。
type State = tuple[int, ...] # 整棵树的当前权值排列
type Swaps = list[tuple[int, int]] # 所有交换方式,统一写成 0 基下标且前者更小
def is_heap(state: State, fa: list[int], n: int) -> bool:
"""state 是否已满足大根堆性质:每个非根结点的序号都小于其父亲的序号。"""
return all(state[fa[i] - 1] < state[i - 1] for i in range(1, n + 1) if fa[i])
def encode(weights: list[int], n: int) -> State:
"""把点权换成序号排列:最小权值的序号是 n-1,最大权值是 0。"""
by_weight = sorted(zip(weights, range(1, n + 1))) # 结点按权值升序
rank = {node: n - 1 - pos for pos, (_, node) in enumerate(by_weight)}
return tuple(rank[node] for node in range(1, n + 1))
def expand(state: State, swaps: Swaps) -> Iterator[State]:
"""逐个产出 state 经过一次交换能到达的排列。"""
for i, j in swaps:
# 交换第 i、j 位:切片拼出「前半段 + j 的值 + 中间段 + i 的值 + 后半段」
yield state[:i] + (state[j],) + state[i + 1:j] + (state[i],) + state[j + 1:]
def min_swaps(start: State, fa: list[int], n: int, swaps: Swaps) -> int:
"""BFS:第一次生成出合法堆排列时的层数就是最少交换次数。"""
if is_heap(start, fa, n):
return 0 # 初始排列已经是堆,一次都不用交换
dist = {start: 0}
queue = deque([start])
while queue:
state = queue.popleft()
for nxt in expand(state, swaps):
if nxt in dist:
continue
dist[nxt] = dist[state] + 1 # BFS 保证首次发现就是最短距离
if is_heap(nxt, fa, n):
return dist[nxt] # 终点是一个集合,命中即答案
queue.append(nxt)
return -1 # 题面保证有解,这里只是兜底
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
fa = [0] + [next(data) for _ in range(n)] # fa[i] = 结点 i 的父亲,0 表示根
weights = [next(data) for _ in range(n)] # weights[i-1] = 结点 i 的点权
swaps: Swaps = []
for _ in range(m):
u, v = next(data), next(data)
swaps.append((u - 1, v - 1) if u < v else (v - 1, u - 1))
print(min_swaps(encode(weights, n), fa, n, swaps))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 15:36
* update_at: 2026-10-07 15:54
*/
// 一本通 1689 堆排问题
//
// 算法:状态压缩 + BFS
// - 点权互不相同,把权值按大小换成序号 0..N-1(最大权值换成 0),
// 大根堆性质就变成「父亲的序号 < 儿子的序号」,与具体数值无关。
// - N <= 16,每个结点用 4 位存序号,整棵树的排列压成一个 64 位整数状态。
// - 一种交换方式就是一条边,边权为 1,同一方式可重复使用。
// 以初始排列为起点跑 BFS,第一次生成出合法的堆排列时所在层数就是最少交换次数。
// - 状态数上界是 N!,开不出数组,visited 只能用 unordered_set(哈希风险见复杂度说明)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; // 状态整数:16 个结点各占 4 位,共 64 位,必须用无符号
const int MAXN = 20;
const int MAXM = 130;
ll N; // 结点个数
ll M; // 交换方式的种数
ll fa[MAXN]; // fa[i] = 结点 i 的父亲,0 表示它是根
ull rank_of[MAXN]; // rank_of[i] = 结点 i 的权值序号,最大权值为 0
// 左侧要左移 4(i-1) 位,用无符号类型才不会在有符号位移上溢出
struct Swap { // 一种交换方式
ll u;
ll v;
};
Swap swp[MAXM]; // swp[1..M] 存所有交换方式,下标从 1 开始和题面一致
// 判断状态 s 是否已经满足大根堆性质:每个结点序号都小于其父亲的序号
bool is_heap(ull s) {
for (ll i = 1; i <= N; i++) {
if (fa[i] == 0) continue; // 根没有父亲,不用比较
ll ps = 4 * (fa[i] - 1); // 父亲在状态里的位偏移
ll cs = 4 * (i - 1); // 结点 i 在状态里的位偏移
if (((s >> ps) & 15ULL) > ((s >> cs) & 15ULL)) return false;
}
return true;
}
// 从初始状态 start 出发做 BFS,返回首次出现堆排列时的交换次数(数据保证有解)
// 逐层扩展:cur 是第 depth 层的全部状态,nxt 是下一层。
// 一个状态一旦被生成出来就立刻判堆:BFS 保证它第一次出现的层数就是最少交换次数,
// 所以命中即可返回,不必等它出队,省下整整一层的哈希表容量。
ll bfs(ull start) {
if (is_heap(start)) return 0; // 初始排列已经是堆,一次都不用交换
unordered_set<ull> vis; // 状态数上界是 N!,开不出数组,只能用哈希表记录访问
vis.reserve(1 << 20);
vis.insert(start);
vector<ull> cur, nxt;
cur.push_back(start);
for (ll depth = 1; !cur.empty(); depth++) {
nxt.clear();
for (size_t k = 0; k < cur.size(); k++) {
ull s = cur[k];
for (ll i = 1; i <= M; i++) {
ll su = 4 * (swp[i].u - 1), sv = 4 * (swp[i].v - 1);
ull a = (s >> su) & 15ULL; // 两个结点的当前序号
ull b = (s >> sv) & 15ULL;
// 清掉这两个 4 位再写回去,就完成一次权值交换
ull t = (s & ~(15ULL << su) & ~(15ULL << sv)) | (b << su) | (a << sv);
if (!vis.insert(t).second) continue;
if (is_heap(t)) return depth;
nxt.push_back(t);
}
}
cur.swap(nxt);
}
return -1; // 题面保证有解,这里只是兜底
}
int main() {
scanf("%lld %lld", &N, &M);
for (ll i = 1; i <= N; i++) scanf("%lld", &fa[i]);
vector<pair<ll, ll> > vw; // (权值, 结点编号),用于把权值换成序号
for (ll i = 1; i <= N; i++) {
ll w;
scanf("%lld", &w);
vw.push_back(make_pair(w, i));
}
for (ll i = 1; i <= M; i++) scanf("%lld %lld", &swp[i].u, &swp[i].v);
sort(vw.begin(), vw.end()); // 权值升序;序号倒过来给,最大权值的序号是 0
for (ll r = 0; r < N; r++) rank_of[vw[r].second] = N - 1 - r;
ull start = 0;
for (ll i = 1; i <= N; i++) start |= rank_of[i] << (4 * (i - 1));
printf("%lld\n", bfs(start));
return 0;
}复杂度
设
- 时间:每个状态枚举
种交换、每次判堆需要 ;由于这里在生成时判堆并立即返回, 判堆次数是 ,总时间 ,即 。 - 空间:哈希表 + 当前层/下一层各存
个 64 位状态,共 。 - 实测:第 7 个测试点(
, ,答案 )访问 个状态, C++ 用时约 ms、峰值内存约 MB;Python 用时约 s、峰值内存约 MB。 其余九个点访问的状态数都在 以内。 - 哈希风险:
unordered_set<unsigned long long>+reserve(1 << 20)在这个状态数下负载因子 仍在以下,实测未出现明显退化;若手写哈希也不需要,直接用库表即可。
总结
- 先离散化,再谈状态。大根堆只关心相对大小,把权值换成
的序号是本题的 第一个关键点:它不仅让"判堆"变成一次下标比较,还顺手把状态编码按到 4 位上。 - 目标是一个集合,不是一个点。这类"到达某种性质"的题不要硬找唯一终点, 把性质写成判据、在 BFS 里即时检查即可。
不是偶然。 位正好塞进一个 uint64, 一个整数同时承担"状态 + 哈希键 + 可比较"三重角色,这是本题写法最省事的地方。- 在生成时判堆能省一整层。BFS 保证状态第一次被生成时的层数就是最短距离,
因此不必等它出队再判,
vis.insert成功的瞬间就能检查;本题最坏的那个点因此 把哈希表从 217 万状态降到 7 万状态,内存从 133 MB 降到 13 MB。 - 题面的样例解释第二组与数据不符。题面写的最优方案是
,其中第 5 步 有误:按这个顺序执行后 序号序列是 ,结点 2 的 比父亲结点 3 的 小,仍然不是堆。 换成 即得到合法的 , 步数同样是数据里答案的 。本文的代码按数据实现,输出 。
最优方案为进行(