洛谷1963 [NOI2009]变换序列_综合

标签：匈牙利算法

题目

题目传送门

题目描述

对于 $N$ 个整数 $\cdots, N-1$ ，一个变换序列 $T$ 可以将 $i$ 变成 $T_i$ ，其中 $T_i \in \{ 0,1,\cdots, N-1\}$ 且 $\bigcup_{i=0}^{N-1} \{T_i\} = \{0,1,\cdots , N-1\}$ 。， $\forall x,y \in \{0,1,\cdots , N-1\}$ ，定义x和y之间的距离 $D(x,y)=min\{|x-y|,N-|x-y|\}$ 。给定每个 $i$ 和 $T_i$ 之间的距离 $D(i,T_i)$ ，你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列，输出其中字典序最小的一个。

说明：对于两个变换序列 $S$ 和 $T$ ，如果存在 $p < N$ ，满足对于 $i=0,1,\cdots p-1$ ， $S_i=T_i$ 且 $S_p<T_p$ ，我们称 $S$ 比 $T$ 字典序小。

输入输出格式

输入格式

第一行包含一个整数 $N$ ，表示序列的长度。接下来的一行包含 $N$ 个整数 $D_i$ ，其中 $D_i$ 表示 $i$ 和 $T_i$ 之间的距离。

输出格式

如果至少存在一个满足要求的变换序列 $T$ ，则输出文件中包含一行 $N$ 个整数，表示你计算得到的字典序最小的 $T$ ；否则输出No Answer（不含引号）。注意：输出文件中相邻两个数之间用一个空格分开，行末不包含多余空格。

输入输出样例

输入样例#1

5
1 1 2 2 1

输出样例#1

1 2 4 0 3

说明

对于30%的数据，满足：N<=50；

对于60%的数据，满足：N<=500；

对于100%的数据，满足：N<=10000。

分析

二分图的完美匹配问题

每个点只与 $(di+i)\%n$ ， $(n-di+i)\%n$ 联通

因为匈牙利算法的本质，是当不匹配的情况下，后面的点把前面的点挤出的过程，所以倒着扫描匹配可以解决字典序最小的问题

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
    ll f=1,x=0;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;
}
//******head by yjjr******
const int maxn=1e4+6;
int n,d[maxn],mt[maxn],ans[maxn],last[maxn<<2],cnt=0;bool vis[maxn];
inline int dis(int x,int y){
    return min(abs(x-y),n-abs(x-y));}
vector <int> e[maxn];
inline bool dfs(int x){
    for(int i=0;i<e[x].size();i++)if(!vis[e[x][i]]){
    vis[e[x][i]]=1;if(mt[e[x][i]]==0||dfs(mt[e[x][i]])){
    mt[e[x][i]]=x;return 1;}}return 0;
}
int main(){
    n=read();rep(i,0,n-1)d[i]=read();rep(i,0,n-1){
    int x=i+d[i],y=i-d[i]+n;x%=n,y%=n;if(dis(x,i)!=d[i])x=-1;if(dis(y,i)!=d[i])y=-1;if(x>y)swap(x,y);if(x!=-1)e[i].push_back(x);if(y!=-1)e[i].push_back(y);}dep(i,n-1,0){
    mem(vis,0);if(!dfs(i)){
    puts("No Answer");return 0;}}rep(i,0,n-1)ans[mt[i]]=i;rep(i,0,n-1)cout<<ans[i]<<' ';cout<<endl;return 0;
}