bzoj1562-[NOI2009]变换序列

Description

bzoj1562-[NOI2009]变换序列

Solution

显然是个二分图最小字典序匹配.

套板子即可.

[模板] 匈牙利算法&&二分图最小字典序匹配

另外, 题中似乎没有保证\(d \le \frac n2\)(否则无解), 需要特判. update:实测不特判也可过

Code

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef double db;
typedef long long ll;

//---------------------------------------

const int nsz=2e4+50;
int n,line[nsz];

int to[nsz][3];
int vi[nsz],mat[nsz];
bool arg(int p){
    rep(i,0,1){
        int v=to[p][i];
        if(vi[v])continue;
        vi[v]=1;
        if(mat[v]==0||arg(mat[v])){
            mat[v]=p,mat[p]=v;
            return 1;
        }
    }
    return 0;
}

int hung(){
    int res=0;
    repdo(i,n-1,0){
        memset(vi,0,sizeof(vi));
        res+=arg(i);
    }
    return res;
}

int getm(int v){return v<0?v+n:v>=n?v-n:v;}
int tr(int v){return v+n;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    int a,tmp=0,t1,t2;
    rep(i,0,n-1){
        cin>>a;
        if(a>n/2){tmp=1;break;}
        t1=getm(i-a),t2=getm(i+a);
        if(t1>t2)swap(t1,t2);
        to[i][0]=t1+n,to[i][1]=t2+n;
    }
    if(tmp){cout<<"No Answer\n";return 0;}

    int ans=hung();
    if(ans<n){cout<<"No Answer\n";return 0;}
    rep(i,0,n-1)cout<<mat[i]-n<<' ';
    cout<<'\n';
    return 0;
}

bzoj1562-[NOI2009]变换序列

原文：https://www.cnblogs.com/ubospica/p/10249792.html