读懂题意后发现这道题最主要是要求出字典序最小的排列, 考察了匈牙利算法的实质.
首先对于 $D_i$ 的定义, 我们可以解出可能的 $T_i$, 然后将 $i$ 与 $T_i$ 连边, 求最大匹配.
如果最大匹配 $<N$ 则说明 $"No\ Answer"$.
但是要求字典序最小.
第一中方法在我 $AC$ 后翻看题解而写的.
这个程序是根据匈牙利算法的实质写的.
对于一个待匹配点, 如果从其中一条非匹配边能匹配上, 则这条匹配边一定会被匹配上.
我们将所有 $i$ 连向 $T_i$ 的边从小到大排序, 从最后一个点开始匹配, 从小的 $T_i$ 到大的 $T_i$ 判断. 最后答案一定是字典序最小的.
为什么呢? 根据刚刚的总结, 也就是能保证第 $1$ 个点一定能选择最好的匹配, 因为非匹配边从最好的往最坏的情况枚举, 匹配上的一定就是最好的, 因为假如前面没有匹配上, 原因就在于选择前面的边一定不能匹配.
- #include <bits/stdc++.h>
- using namespace std;
- #define re register
- #define rep(i, a, b) for (re int i = a; i <= b; ++i)
- #define repd(i, a, b) for (re int i = a; i>= b; --i)
- #define maxx(a, b) a = max(a, b);
- #define minn(a, b) a = min(a, b);
- #define LL long long
- #define inf (1 <<30)
- inline int read() {
- int w = 0, f = 1; char c = getchar();
- while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
- while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
- return w * f;
- }
- const int maxn = 1e4 + 5;
- int N, D[maxn], e[maxn][5], s[maxn], t[maxn];
- int lk[maxn], pt[maxn], vis[maxn];
- bool find(int u, int tag) {
- rep(i, s[u], t[u]) {
- int v = e[u][i];
- if (vis[v] != tag) {
- vis[v] = tag;
- if (lk[v] == -1 || find(lk[v], tag)) {
- lk[v] = u;
- pt[u] = v;
- return true;
- }
- }
- }
- return false;
- }
- int main() {
- N = read();
- rep(i, 0, N-1) {
- D[i] = read();
- e[i][1] = D[i]+i, e[i][2] = i-D[i], e[i][3] = N+i-D[i], e[i][4] = D[i]-N+i;
- sort(e[i]+1, e[i]+5);
- s[i] = 1, t[i] = 4;
- while (s[i] <= 4 && e[i][s[i]] < 0) s[i]++;
- while (t[i]> 0 && e[i][t[i]]>= N) t[i]--;
- }
- memset(vis, -1, sizeof(vis));
- memset(lk, -1, sizeof(lk));
- repd(i, N-1, 0)
- if (!find(i, i)) {
- printf("No Answer");
- return 0;
- }
- rep(i, 0, N-1)
- printf("%d", pt[i]);
- return 0;
- }
第二种方法是我自己想到的, 比上面的代码复杂.
首先有一点: 由非匹配边和匹配边交替构成的回路 (断句) 翻转所有边的匹配与否 (断句) 得到的是另一种匹配.
所以我们先找出一个最大匹配, 再通过上面的结论从第一个点调整使得解更优. 最后同样也能得到字典序最小的匹配.
- #include <bits/stdc++.h>
- using namespace std;
- #define re register
- #define rep(i, a, b) for (re int i = a; i <= b; ++i)
- #define repd(i, a, b) for (re int i = a; i>= b; --i)
- #define maxx(a, b) a = max(a, b);
- #define minn(a, b) a = min(a, b);
- #define LL long long
- #define inf (1 <<30)
- inline int read() {
- int w = 0, f = 1; char c = getchar();
- while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
- while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
- return w * f;
- }
- const int maxn = 1e4 + 5;
- int N, D[maxn], e[maxn][5], s[maxn], t[maxn];
- int lk[maxn], pt[maxn], vis[maxn];
- bool find(int u, int tag) {
- rep(i, s[u], t[u]) {
- int v = e[u][i];
- if (vis[v] != tag) {
- vis[v] = tag;
- if (lk[v] == -1 || find(lk[v], tag)) {
- lk[v] = u;
- pt[u] = v;
- return true;
- }
- }
- }
- return false;
- }
- bool dfs(int u, int rt) {
- rep(i, s[u], t[u]) {
- int v = e[u][i];
- if (lk[v] < rt) continue;
- if (v == pt[u]) {
- if (u == rt) return false;
- continue;
- }
- if (vis[v] != rt) {
- vis[v] = rt;
- if (lk[v] == rt || dfs(lk[v], rt)) {
- lk[v] = u;
- pt[u] = v;
- return true;
- }
- }
- }
- return false;
- }
- int main() {
- N = read();
- rep(i, 0, N-1) {
- D[i] = read();
- e[i][1] = D[i]+i, e[i][2] = i-D[i], e[i][3] = N+i-D[i], e[i][4] = D[i]-N+i;
- sort(e[i]+1, e[i]+5);
- s[i] = 1, t[i] = 4;
- while (s[i] <= 4 && e[i][s[i]] < 0) s[i]++;
- while (t[i]> 0 && e[i][t[i]]>= N) t[i]--;
- }
- memset(vis, -1, sizeof(vis));
- memset(lk, -1, sizeof(lk));
- rep(i, 0, N-1)
- if (!find(i, i)) {
- printf("No Answer");
- return 0;
- }
- memset(vis, -1, sizeof(vis));
- rep(i, 0, N-1)
- dfs(i, i);
- rep(i, 0, N-1)
- printf("%d", pt[i]);
- return 0;
- }
[NOI2009]变换序列
来源: http://www.bubuko.com/infodetail-2944326.html