题目地址：洛谷：【P1963】[NOI2009]变换序列 – 洛谷、BZOJ：Problem 1562. — [NOI2009]变换序列

题目描述

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

说明：对于两个变换序列 S 和 T ，如果存在 p<N ，满足对于 i=0,1,⋯p-1 ， Si=Ti 且 Sp<Tp ，我们称 S 比 T 字典序小。

输入输出格式

输入格式：
第一行包含一个整数 N ，表示序列的长度。接下来的一行包含 N 个整数 Di ，其中 Di 表示 i 和 Ti 之间的距离。

输出格式：
如果至少存在一个满足要求的变换序列 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。

题解

从i向可能的Di连有向边，其实是个二分图匹配，如果匹配不够n，则无解。有解要求输出字典序最小的答案，这需要一些思考。匈牙利算法的流程中，实际上是按顺序扩展增广路上点的集合的，因此如果倒序求增广路，可能更小的点会替代原来匹配上的更大的点，然后再把每个点的出边表从小到大排个序，就可以实现字典序最小。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 20005;

int n;

std::vector<int> gra[MAXN];

int match[MAXN];
bool vis[MAXN];

inline bool dfs(int u) {
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!vis[v]) {
            vis[v] = true;
            if(match[v] == -1 || dfs(match[v])) {
                match[v] = u; match[u] = v; return true;
            }
        }
    }
    return false;
}

inline int bmatch() {
    int res = 0;
    memset(match, -1, sizeof(match));
    for(int i = n - 1; i >= 0; i--) {
        if(match[i] == -1) {
            memset(vis, 0, sizeof(vis));
            if(dfs(i)) res++;
        }
    }
    return res;
}

int d[MAXN];

int main() {
    n = readint();
    for(int i = 0; i < n; i++) {
        d[i] = readint();
    }
    for(int i = 0; i < n; i++) {
        gra[i].push_back((i + d[i]) % n + n);
        gra[i].push_back((i - d[i] + n) % n + n);
    }
    for(int i = 0; i < n << 1; i++) {
        std::sort(gra[i].begin(), gra[i].end());
    }
    if(bmatch() < n) {
        puts("No Answer");
    } else {
        for(int i = 0; i < n; i++) {
            printf("%d ", match[i] - n);
        }
    }
    return 0;
}