【解题报告】BZOJ 1562 [NOI2009]变换序列

发表于

传送门

$\text{Solution}$

很容易就能够想到位置和位置上可能的数相匹配，这样子就是二分图最大匹配的问题。

可是那么简单，最有意思的操作在于匹配要求字典序。

这么一来我们要思考一下二分图匈牙利算法实现的特点。

匈牙利算法存在“反悔”操作，也就是说前面匹配好的如果后面需要的话可能会把当前的顶掉，换句话说，假如之前贪心找到最小的匹配过去，会被后面的给顶掉。

为了保证前面的字典序最小，我们需要倒序匹配 ，即让后面的先匹配，这样的话就可以保证前面的字典序最小，从而保证整体的字典序最小。

说完了匈牙利的事，接下来讲讲加边需要注意的地方。

看得出来这个边肯定不能乱加吧。。。在匈牙利具体匹配的过程中，我们对每一个位置需要优先选择小的数以保证字典序，所以找到合法的数字之后要排个序，如果是 $\text{vector}$ 存边的话直接加进去，前向星链表存边的话要注意遍历边表的时候是倒序遍历的（先加进去的边后被遍历到），所以要将边从大到小加入。

$\text{Code}$

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10005
#define judge(x) (0 <= (x) && (x) < n)
struct edgeType {
	int to, next;
} edge[N << 2];
int head[N];
inline void addEdge(int from, int to) {
	static int cnt = 0;
	edge[++cnt] = (edgeType){to, head[from]};
	head[from] = cnt;
}
int match[2][N], d[N];
bool visit[N];
inline int dfs(int u) {
	for (int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (!visit[v]) {
			visit[v] = true;
			if (match[1][v] == -1 || dfs(match[1][v])) {
				match[0][u] = v;
				match[1][v] = u;
				return 1;
			}
		}
	}
	return 0;
}
inline int MaxMatch(int n) {
	int ans = 0;
	memset(match, -1, sizeof match);
	for (int i = n - 1; i >= 0; i--)
		if (match[0][i] == -1) {
			memset(visit, false, sizeof visit);
			ans += dfs(i);
		}
	return ans;
}
int main() {
	std::ios::sync_with_stdio(false);
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> d[i];
		static int cnt, a[4];
		cnt = 0;
		if (judge(i - d[i])) a[cnt++] = i - d[i];
		if (judge(i + d[i])) a[cnt++] = i + d[i];
		if (judge(i - (n - d[i]))) a[cnt++] = i - (n - d[i]);
		if (judge(i + (n - d[i]))) a[cnt++] = i + (n - d[i]);
		std::sort(a, a + cnt, std::greater<int>());
		for (int j = 0; j < cnt; j++) addEdge(i, a[j]);
	}
	if (MaxMatch(n) < n) std::cout << "No Answer" << std::endl;
	else {
		for (int i = 0; i < n; i++)
			std::cout << match[0][i] << " ";
		std::cout << std::endl;
	}
	return 0;
}