BZOJ1562 [NOI2009]变换序列 【KM算法】

题目

输入格式

输出格式

输入样例

5

1 1 2 2 1

输出样例

1 2 4 0 3

提示

30%的数据中N≤50；

60%的数据中N≤500；

100%的数据中N≤10000。

题解

每个位置可以和两种数匹配，显然是一个二分图匹配问题

但要求字典序最小，我们就按字典序存边

由于在KM算法中，后来着具有更高的优先级，我们倒序匹配即可

#include<iostream>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

#include<algorithm>

#define LL long long int

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

using namespace std;

const int maxn = 10005,maxm = 100005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int lk[maxn],vis[maxn],ans[maxn];

int h[maxn],ne = 1;

struct EDGE{int to,nxt;}ed[maxn << 1];

inline void build(int u,int v){

	ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;

}

bool find(int u){

	Redge(u) if (!vis[to = ed[k].to]){

		vis[to] = true;

		if (lk[to] == -1 || find(lk[to])){

			lk[to] = u;

			return true;

		}

	}

	return false;

}

int n,a[maxn],b[maxn];

int main(){

	memset(lk,-1,sizeof(lk));

	n = read(); int tmp,a,b;

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

		tmp = read();

		a = (i + tmp) % n;

		b = (i - tmp + n) % n;

		if (a < b) swap(a,b);

		build(i,a); build(i,b);

	}

	for (int i = n - 1; i >= 0; i--){

		memset(vis,0,sizeof(vis));

		if (!find(i)){

			puts("No Answer");

			return 0;

		}

	}

	for (int i = 0; i < n; i++) ans[lk[i]] = i;

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

		printf("%d",ans[i]);

		if (i < n - 1) printf(" ");

	}

	return 0;

}