BZOJ1562 (变换序列)[二分图匹配，匈牙利算法]

发表于 | 更新于 | | 阅读次数：

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1562

求出一个满足要求的T序列比较容易想，只需要从i向加上距离后对应的点连边，然后就是一个二分图匹配问题了。
麻烦的是要输出字典序最小的T，这里要注意两点：一是连边的时候要小的数在前，二是在跑匈牙利算法的时候一定要倒着搜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN=10009;
vector<int> V[MAXN*2];
int linker[MAXN*2];
bool used[MAXN*2];
int n;
bool dfs(int u) {
	for(int i=0;i<V[u].size();i++) {
		int v=V[u][i];
		if(!used[v]) {
			used[v]=true;
			if(linker[v]==-1 || dfs(linker[v])) {
				linker[v]=u;
				return true;
			}
		}
	}
	return false;
}
int hungary() {
	int res=0;
	memset(linker,-1,sizeof(linker));
	for(int u=n-1;u>=0;u--) { //注意是倒序
		memset(used,false,sizeof(used));
		if(dfs(u)) res++;
	}
	return res;
}

void add(int u,int v) {
	V[u].push_back(v);
}
int seq[MAXN];
int main() {
	int dis;
	scanf("%d",&n);
	for(int i=0;i<n;i++) {
		scanf("%d",&dis);
		if(dis>n/2) {
			printf("No Answer");
			return 0;
		}
		int a=i-dis;
		while(a<0) a+=n;
		int b=i+dis;
		b%=n;
		if(a>b) swap(a,b);
		add(i,a+n);
		if(a!=b) add(i,b+n);
	}
	int cnt=hungary();
	if(cnt<n) {
		printf("No Answer");
		return 0;
	}
	for(int i=n;i<n*2;i++) {
		seq[linker[i]]=i-n;
	}
	for(int i=0;i<n;i++) {
		printf(i<n-1?"%d ":"%d",seq[i]);
	}
}