先判断愿望关系能否构成唯一的整环，再在正反两个环序中统计最优旋转能保留多少人不动，答案就是 n 减去这个最大值。
OJ: luogu
题目 ID: P1053
难度:普及+/提高
标签:图论构造环形处理思维
日期: 2026-06-20 17:14
题意
有 n 个同学一开始按 1,2,...,n 围成一个圈。
第 i 个同学给出两个自己最希望相邻的人。
一次操作可以选出若干个同学，让他们整体做一次循环换位，代价等于这次被移动的人数。
问能否调整到一个满足所有人愿望的围圈方案；如果能，最小总代价是多少。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据暴力解。
// 直接枚举所有最终环形座次，检查是否满足每个人的愿望，
// 再统计这一排座次相对初始状态有多少人离开了原位。
const int MAXN = 15;
int n;
int want1[MAXN], want2[MAXN];
// 判断学生 u 在当前环里左右两边的人，是否正好是他想要的两个人。
bool check_one_student(int u, int left_student, int right_student) {
if (left_student == want1[u] && right_student == want2[u]) {
return true;
}
if (left_student == want2[u] && right_student == want1[u]) {
return true;
}
return false;
}
// 检查整圈人是否满足所有愿望。
bool check_circle(const vector<int> &perm) {
for (int i = 0; i < n; i++) {
int u = perm[i];
int left_student = perm[(i - 1 + n) % n];
int right_student = perm[(i + 1) % n];
if (!check_one_student(u, left_student, right_student)) {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> want1[i] >> want2[i];
}
vector<int> perm;
for (int i = 1; i <= n; i++) {
perm.push_back(i);
}
int ans = -1;
do {
if (!check_circle(perm)) {
continue;
}
int moved = 0;
for (int i = 0; i < n; i++) {
if (perm[i] != i + 1) {
moved++;
}
}
if (ans == -1 || moved < ans) {
ans = moved;
}
} while (next_permutation(perm.begin(), perm.end()));
cout << ans << '\n';
return 0;
}brute.cpp 直接枚举所有最终座次，检查这一圈是否满足每个人的愿望，然后取最小答案。
这个思路只适合很小的数据，因为它需要枚举全排列。
先把每个人和他希望相邻的两个人连成无向边。 样例会得到下面这张愿望图：
graph G {
1 -- 3;
1 -- 4;
2 -- 3;
2 -- 4;
}
这张图展示的就是“最终谁必须和谁相邻”。 如果图里有一条边不是双方互相承认的，或者整张图不是一个包含全部同学的单环，那就一定无解。 因为真正围成一个圈时，每个人最终都只能有两个邻居，而且所有人必须在同一个大圈里。
所以先做两个判定：
- 愿望关系必须对称；
- 整张愿望图必须是一整个
n个点的单环。
一旦这个环存在，最终合法座次其实只剩两种写法：
- 沿着环正着写；
- 沿着环反着写。
同一个方向下，不同方案只差一个整体旋转。
接下来考虑代价。
如果最终某个同学不在原来的位置上，那么他至少要被移动一次，所以总代价不会小于“离开原位的人数”。
反过来，把初始座次到目标座次看成一个置换。
这个置换可以拆成若干个不相交的置换环。
长度为 k 的置换环，可以直接用一次长度为 k 的循环换位命令完成，代价正好是 k。
所以最小总代价，恰好等于最终离开原位的人数。
于是问题变成：
- 在正向环序和反向环序的所有整体旋转中，哪一个能让留在原位置的人数最多？
设某个方向下写出的环序是 order[0..n-1]。
对学生 x 来说，他原来的位置是 x-1。
如果 x 现在位于 order[pos]，那么只有一个固定的旋转量，能把他转回到原位。
所以只要对每个学生都算出这个旋转量，并给这个旋转量记一票：
- 一种旋转量得到多少票
- 就表示这种整体旋转能保留多少个人不动
对正向和反向都各统计一次，取最大保留人数 best_keep，答案就是：
text
n - best_keep代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
int n;
int want1[MAXN], want2[MAXN];
vector<int> g[MAXN];
int order_a[MAXN], order_b[MAXN];
int shift_cnt[MAXN];
bool vis[MAXN];
// 判断 u 是否把 v 当成自己希望相邻的同学。
bool like_each_other(int u, int v) {
return want1[u] == v || want2[u] == v;
}
// 检查输入本身是否可能对应一个合法的环。
bool check_basic() {
for (int i = 1; i <= n; i++) {
if (want1[i] == i || want2[i] == i) {
return false;
}
if (want1[i] == want2[i]) {
return false;
}
}
for (int i = 1; i <= n; i++) {
if (!like_each_other(want1[i], i)) {
return false;
}
if (!like_each_other(want2[i], i)) {
return false;
}
}
return true;
}
// 判断“愿望图”是否是一整个 n 个点的单环。
bool check_connected_cycle() {
queue<int> q;
int visited_cnt = 0;
memset(vis, 0, sizeof(vis));
vis[1] = true;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
visited_cnt++;
for (int i = 0; i < (int)g[u].size(); i++) {
int v = g[u][i];
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
return visited_cnt == n;
}
// 从 1 号点出发，沿着一个方向把整条环序写出来。
bool build_order(int start_next, int order_arr[]) {
memset(vis, 0, sizeof(vis));
order_arr[0] = 1;
order_arr[1] = start_next;
vis[1] = true;
vis[start_next] = true;
for (int i = 2; i < n; i++) {
int prev = order_arr[i - 2];
int u = order_arr[i - 1];
int nxt = (g[u][0] == prev ? g[u][1] : g[u][0]);
if (vis[nxt]) {
return false;
}
order_arr[i] = nxt;
vis[nxt] = true;
}
int last = order_arr[n - 1];
bool close_to_one = false;
for (int i = 0; i < 2; i++) {
if (g[last][i] == 1) {
close_to_one = true;
}
}
return close_to_one;
}
// 对一个固定方向的环序，统计所有旋转里最多能保留多少人不动。
int calc_best_keep(int order_arr[]) {
int best = 0;
for (int i = 0; i < n; i++) {
shift_cnt[i] = 0;
}
for (int pos = 0; pos < n; pos++) {
int student = order_arr[pos];
int original_pos = student - 1;
int shift = pos - original_pos;
shift %= n;
if (shift < 0) {
shift += n;
}
shift_cnt[shift]++;
}
for (int i = 0; i < n; i++) {
best = max(best, shift_cnt[i]);
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> want1[i] >> want2[i];
g[i].push_back(want1[i]);
g[i].push_back(want2[i]);
}
if (!check_basic()) {
cout << -1 << '\n';
return 0;
}
if (!check_connected_cycle()) {
cout << -1 << '\n';
return 0;
}
if (!build_order(g[1][0], order_a)) {
cout << -1 << '\n';
return 0;
}
// 反方向的环序，就是把正方向除了 1 号之外反过来。
order_b[0] = order_a[0];
for (int i = 1; i < n; i++) {
order_b[i] = order_a[n - i];
}
int best_keep = max(calc_best_keep(order_a), calc_best_keep(order_b));
// 每个最终不在原位的人至少要被移动一次；
// 而一个置换环可以用一次循环换位直接完成，所以答案就是“离开原位的人数”。
cout << n - best_keep << '\n';
return 0;
}复杂度
时间复杂度是
总结
这题表面上是在优化一串换位操作，真正的关键有两个：
- 满足愿望的最终座次，实际上被“愿望图是一整个单环”完全限定住了；
- 操作代价可以化成“最后有多少人离开原位”。
把这两个结论接起来，原题就变成了一个很干净的图论判定 + 环形统计问题。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
