【BZOJ1562】【NOI2009】变换序列

二分图最小字典序匹配

倒过来dfs匈牙利就行了

// <1562.cpp> - Fri Sep 23 08:10:53 2016
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=20010;
const int MAXM=80010;
const int INF=1e9;
int bt=1,b[MAXN],next[MAXM],to[MAXM];
inline void add(int x,int y){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;
}
int match[MAXN];
bool in[MAXN];
bool dfs(int x){
    if(in[x])return 0;
    in[x]=1;
    for(int i=b[x];i;i=next[i])
        if(!match[to[i]]||dfs(match[to[i]])){
            match[x]=to[i];
            match[to[i]]=x;
            in[x]=0;
            return 1;
        }
    in[x]=0;
    return 0;
}
int main(){
    int n=gi();
    for(int i=1;i<=n;i++){
        int d=gi();
        int x=(i+d-1)%n+1,y=(i-d+n-1)%n+1;
        if(x>y)swap(x,y);
        add(i,n+y);
        add(i,n+x);
    }
    int ans=0;
    for(int i=n;i;i--)if(!match[i]&&dfs(i))ans++;
    if(ans!=n){printf("No Answer");return 0;}
    for(int i=1;i<n;i++)printf("%d ",match[i]-n-1);
    printf("%d",match[n]-n-1);
    return 0;
}

// <1562.cpp> - Fri Sep 23 08:10:53 2016

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=20010;

const int MAXM=80010;

const int INF=1e9;

int bt=1,b[MAXN],next[MAXM],to[MAXM];

inline void add(int x,int y){

next[++bt]=b[x];b[x]=bt;to[bt]=y;

next[++bt]=b[y];b[y]=bt;to[bt]=x;

}

int match[MAXN];

bool in[MAXN];

bool dfs(int x){

if(in[x])return 0;

in[x]=1;

for(int i=b[x];i;i=next[i])

if(!match[to[i]]||dfs(match[to[i]])){

match[x]=to[i];

match[to[i]]=x;

in[x]=0;

return 1;

}

in[x]=0;

return 0;

}

int main(){

int n=gi();

for(int i=1;i<=n;i++){

int d=gi();

int x=(i+d-1)%n+1,y=(i-d+n-1)%n+1;

if(x>y)swap(x,y);

add(i,n+y);

add(i,n+x);

}

int ans=0;

for(int i=n;i;i--)if(!match[i]&&dfs(i))ans++;

if(ans!=n){printf("No Answer");return 0;}

for(int i=1;i<n;i++)printf("%d ",match[i]-n-1);

printf("%d",match[n]-n-1);

return 0;

}