洛谷P1963 [NOI2009] 变换序列 题解

题目链接：P1963 [NOI2009] 变换序列

题意：

对于 $N$ 个整数 $0, 1, \cdots, N-1$ ，一个变换序列 $T$ 为这 $N$ 个整数的一个置换。

定义 $x$ 和 $y$ 之间的距离（$x,y = 0,1,\cdots,n-1$）

$$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（不含引号）。注意：输出文件中相邻两个数之间用一个空格分开，行末不包含多余空格。

数据范围：

对于 $100\%$ 的数据，满足：$N\le 10^4$。

这道题很好的考察了对匈牙利算法的理解。

注意到这是一个置换，即满足双射的关系，考虑建立二分图。

对于每个左侧 $x$ ，我们可以将它与右侧 $x+D_x,~x-D_x,~x-n+D_x,~x+n-D_x$ 连边

实际上，$x+D_x \le n$ 时，$x-n+D_x \le 0$ ，因此这四条边里面只会有两条存在

不难发现他们就是 $(x+D_x) \bmod n,~(x+n-D_x) \bmod n$

因此如果这张图存在二分图完美匹配，就一定有解。

但是题目要求的是字典序最小的解，这个有些麻烦。

考虑匈牙利算法的过程。

对于顺序枚举的每个点 $u$ ，它会遍历它所有的边 $(u,v_i)$ （按照存储顺序）并尝试匹配。

• 如果 $v_i$ 没有被匹配过，那么它会被直接匹配。

• 如果 $v_i$ 存在匹配的左部点，那就递归地“强行”让之前的点换匹配。

  直到 $v_i$ 可以被匹配，或者发现之前的点改不了匹配（也就是 $v_i$ 无论如何也匹配不了）

不难发现匈牙利算法会使每个后匹配的点 $u$ ，优先匹配它最前的一条边 $(u,v_i)$ 的 $v_i$ 。

如果把 $u$ 的每条边 $(u,v)$ ，按 $v$ 的大小顺序排序后存储

那么对于每个后匹配的点 $u$ ，它会优先匹配最小的一个 $v_i$ 。

注意到字典序是第一个值优先，而匈牙利算法是最后一个匹配的优先

因此我们倒着匹配就可以得到字典序最小的解

时间复杂度 $O(nm)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,to[N][2],p[N],g[N],used[N];
bool dfs(int u,int tim)
{
    for(int t=0; t<2; t++)
    {
        int v=to[u][t];
        if(used[v] != tim) // !used[v];
        {
            used[v] = tim; // used[v]=1;
            if(p[v] == -1 || dfs(p[v],tim))
                { p[v] = u; g[u] = v; return 1; }
        }
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=0,x; i<n; i++)
    {
        cin >> x;
        to[i][0] = (i + x) % n;
        to[i][1] = (i - x + n) % n;
        if(to[i][0] > to[i][1]) swap(to[i][0], to[i][1]); // v1 < v2
    }
    memset(p,-1,sizeof(p));
    int tim=0,i;
    for(i=n-1; i>=0; i--) if(!dfs(i,++tim)) break;
    if(~i) cout << "No Answer\n";
    else for(int i=0; i<n; i++) cout << g[i] << " \n"[i==n-1];
    return 0;
}