洛谷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;
}