[NOIP 2005 提高组] 篝火晚会
link
\(Solution：\)
首先考虑如何判断无解。
无解判法
可以发现当\(A\)想要与\(B\)相邻，但\(B\)却不想与\(A\)相邻时，一定无解。
也就是图中一定都是双向边，同时形成一个环。
但要注意当原图中有多个环时，也是无解的。
所以当且仅当满足一下两个条件中的任意一个时，该问题无解：
1.\(A\)想要与\(B\)相邻，但\(B\)却不想与\(A\)相邻；
2.图不联通。
如果有解，那么原图一定形成了一个环。
而这个环就是最终的期望序列，记为\(B\)。
记初始序列为\(A\)，则\(A={1,2,3,...,n-1,n}\)。
虽然\(B\)已经确定，但是\(B\)是一个环，与\(A\)有\(2n\)中匹配方式（正倒各\(n\)种）。
那么我们考虑对于固定的\(A\)和\(B\)，如何计算答案。
计算方法
可以发现\(A\)和\(B\)都是两个排列，那么这就是一个经典的排列置换问题。
将\(B_i\)与\(i\)连边，这样原图中会形成若干个环。
对于每一个点数大于 2 的环，都需要花费点数的代价将其处理。
那么答案也就相当于\(n-\sum{[B_i==i]}\)。
如果我们直接枚举\(B\)，时间复杂度:\(O(n^2)\)，可以得到 30 pts。
可以发现，我们本质上要让\(\sum{[B_i==i]}\)最大。
也就是让尽可能多的\(B_i=i\)。
而要想让\(B_i=i\)，则需要变换\((B_i-i) \ mod \ n\)次。
那么对于每个\((B_i-i) \ mod \ n\)开桶记录，去最大值，就是答案最大的转法。
记最大值为\(c\)，则最小总代价为\(n-c\)。
时间复杂度：\(O(n)\)。
code
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 1e10
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=1e5+5;
const int mod=998244353;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
bool vis[N];
int n,pos[N],top,cnt[N];
pair<int,int> p[N];
map<pair<int,int>,bool>mp;
vector<int>E[N];
inline void dfs(int x,int fa){vis[x]=1;pos[++top]=x;for(auto to : E[x]){if(vis[to]) continue;dfs(to,x);}return ;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for(int i=1,x,y;i<=n;i++){cin>>x>>y;p[i]={x,y};mp[{i,x}]=1;mp[{i,y}]=1;}bool ok=1;for(int i=1;i<=n;i++){int x=p[i].first,y=p[i].second;if(!mp[{x,i}] || !mp[{y,i}]) ok=0;}if(!ok){cout<<"-1\n";exit(0);}for(int i=1;i<=n;i++){int x=p[i].first,y=p[i].second;E[i].push_back(x);E[i].push_back(y);}dfs(1,0);if(top<n){cout<<"-1\n";exit(0);}for(int i=1;i<=n;i++)cnt[((i-pos[i])%n+n)%n]++;int ans=inf,Max=0;for(int i=0;i<n;i++) Max=max(Max,cnt[i]),cnt[i]=0;for(int i=1;i<=n;i++)cnt[((pos[i]-(n-i+1))%n+n)%n]++;ans=min(ans,n-Max); Max=0;for(int i=0;i<n;i++) Max=max(Max,cnt[i]);ans=min(ans,n-Max);cout<<ans<<'\n';return 0;
}