【洛谷P1963】变换序列

题目大意：对于一个顺序序列，求一个合法置换，可以满足一些约束，若存在多个合法置换，则输出字典序最小的一个置换。

题解：对于序列的置换是否有解的问题，可以和二分图的完美匹配相关联。由于是字典序最小，显然需要贪心考虑。在匈牙利算法执行的过程中，对于每个点来说，可以优先匹配符合条件的最小的点；对于左边点集来说，可以从后往前进行匹配，这样可以保证字典序小的点更可能抢到字典序小的点。

代码如下

#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int maxn=1e4+10;

vector<int> G[maxn];
int n,match[maxn],t[maxn];
bool vis[maxn];

void read_and_parse(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int d;scanf("%d",&d);
        int x=(i-d+n)%n,y=(i+d)%n;
        G[i].pb(x),G[i].pb(y);
    }
    for(int i=0;i<n;i++)sort(all(G[i]));
}

bool dfs(int u){
    for(auto v:G[u])if(!vis[v]){
        vis[v]=1;
        if(!match[v]||dfs(match[v])){
            match[v]=u;return 1;
        }
    }
    return 0;
}

void solve(){
    int ret=0;
    for(int i=n-1;i>=0;i--){
        memset(vis,0,sizeof(vis));
        if(dfs(i))++ret;
    }
    if(ret<n)return (void)puts("No Answer");
    for(int i=0;i<n;i++)t[match[i]]=i;
    for(int i=0;i<n;i++)printf("%d ",t[i]);
    puts("");
}

int main(){
    read_and_parse();
    solve();
    return 0;
}

【洛谷P1963】变换序列

原文：https://www.cnblogs.com/wzj-xhjbk/p/10779300.html