「Bzoj 1562」「NOI2009」变换序列 (二分图最大匹配 / 贪心)

发表于 | 分类于 | | + s

BZOJ 1562
题意：初始有一个序列$[0,n-1]$升序排列$a_i$，然后给出每个位置的$D=\min(∣T_i−a_i∣,N−∣T_i−a_i∣)$，然后你要找到一组字典序最小的方案$T_i$

显然一个$a_i$对应两个$T$: (i + d) % n + 1, ((i - d) % n + n) % n + 1
构造二分图，左边是$a_i$，右边是$T$，连边，就是求一个最大匹配。
但是匈牙利求不一定字典序最小，我们强制让匈牙利先连序号小的点，这样是不是对的呢？
答案是否定的，因为后面不能匹配就会动到前面的匹配，这样就不最优了。
其实可以倒过来求匈牙利，这样就能保证前面的要最小边能够从后面的修正得到。具体证明可以参见NOI 2009 变换序列 - BYVoid，本文下面也搬运了一份。

这题其实类似于Luogu 2526，都是一个位置有多个选择，并且这些选择都是一个集合的，然后就可以考虑二分图最大匹配。

其实这类问题写暴力时就会发现时间复杂度瓶颈于多个选择。

知识点
原来$0$的改为$1$时注意!x的判断修改

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;
    int cnt, n, lk[MAXN], vis[MAXN], flk[MAXN];
    vector<int> G[MAXN];

    bool hungary(int u) {
        for (int i = 0; i < (int)G[u].size(); i++) {//枚举每个右边的点匹配 
            int v = G[u][i];
            if (vis[v] != cnt) {//尝试修改过的节点就不需要遍历了
                vis[v] = cnt;
                if (!lk[v] || hungary(lk[v])) {
                    lk[v] = u, flk[u] = v;
                    return true;//成功匹配 
                }
            }
        }
        return false;
    }
    void clean() {}
    int solve() {

        clean();
        cin >> n;
        for (int d, i = 0; i < n; ++i) {
            scanf("%d", &d);
            int t1 = (i + d) % n + 1;
            int t2 = ((i - d) % n + n) % n + 1;
            if (t1 > t2) swap(t1, t2);
            G[i + 1].push_back(t1 + n), G[i + 1].push_back(t2 + n);
        }

        int ans = 0;
        for (int i = n; i >= 1; --i) 
            ans += hungary(cnt = i);

        if (ans != n) return puts("No Answer");

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

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

搬运自 NOI 2009 变换序列 - BYVoid
算法证明
实现简单的方法往往证明并不容易，该算法运用了贪心的思想。首先我们可以发现，有一些可以直接确定的匹配，这些就是度为1的顶点，必须与其唯一的对应点对应。样例如图2所示，(1,2),(4,3)一定存在于任意一个解中（如果有解的话）。这样的话，我们就可以把已经确定的顶点去除，删除后如果又发现了剩余度为1的顶点，那么继续去除，直到不存在为止。
剩下的顶点中，X集合顶点个数一定与Y集合顶点个数相等。X集合每个顶点的度都是2，所以Y集合中的所有顶点度也都是2。于是剩下的顶点构成了若干个互不连同的环，每个顶点属于且只属于一个环，我们只需在此图上求字典序最小的匹配即可。每个环的匹配只有两种方式，如果我们从环上X集合中序号最小的顶点贪心的选择与序号较小的点匹配，那么该环上的匹配就是字典序最小。样例如图3。
由于事先不知道那些顶点在环上，哪些可以直接确定。从X集合每个顶点倒序查找增广路，就可以保证最后的最优，也就是字典序尽量小。因为如果一个顶点在环上，找到的一定是环上较优的匹配方式，而不在环上的点也可以被后来的增广而修正。

图2
Markdown
图3
Markdown

解法4 贪心
算法描述
按照解法3证明中的描述，我们可以预处理所有已经确定的匹配，并在图中删去。对于剩下的每个环，只需从序号最小的点开始深度优先搜索，并进行匹配即可。
算法证明
证明同解法3。

------ 本文结束 ------