20231109题解

发表于 2023-11-09 分类于信奥，题解阅读次数：

keys

\(\mathcal{Link}\)

似乎题解区还没有讲过可以通过的网络流算法。这里来一发线段树优化。

二分图最大匹配

既然是最小化最大值，考虑二分。在确定限制时间的情况下，每个人能够拿哪些钥匙是可以枚举确定的。

一个人必须且只能对应一个钥匙，相当于把人看成左部，钥匙看成右部，如果人能拿某个钥匙就连边，求人与钥匙的二分图最大匹配。

使用匈牙利算法可获得 50 pts。时间复杂度 \(\mathcal{O}(nm\log W),m=\mathcal{O}(nk)\)。

关于匈牙利算法，出门转 OI-Wiki。

const int maxn = 2e3 + 5;
int n, k, p, mid;
int a[maxn], b[maxn];
int linkto[maxn];
bool vis[maxn];

bool dfs(int u) {
    for (int i = 1; i <= k; i++) {
        if (abs(b[i] - a[u]) + abs(b[i] - p) <= mid) {
            if (!vis[i]) {
                vis[i] = true;
                if (!linkto[i] || dfs(linkto[i])) {
                    return linkto[i] = u, true;
                }
            }
        }
    }
    return false;
}

bool check() {
    memset(linkto, 0, sizeof linkto);
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof vis);
        if (!dfs(i)) return false;
    }
    return true;
}

int main() {
    // freopen("key.in", "r", stdin);
    // freopen("key.out", "w", stdout);
    read(n); read(k); read(p);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= k; i++) read(b[i]);
    int l = 0, r = 1e9;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check()) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

优化-网络流

我们可以使用最大流算法来优化二分图最大匹配。关于最大流，请再次出门。

如果你使用的是 dinic 算法，时间复杂度的上界是 \(\mathcal{O}(\sqrt nm \log W)\)。不过只是个上界，网络流的复杂度比较玄学。这里使用 ISAP 实现，会更优一点。

const int maxn = 3e3 + 5, maxm = 4e6 + 5;
int n, k, p, mid;
int a[maxn], b[maxn];

struct node {
    int v, w, nxt;
} e[maxm];
int head[maxn], cnt = 1, cur[maxn], dep[maxn], gap[maxn];
int s, t;
queue<int> q;

void bfs() {
    memset(dep, -1, sizeof dep); memset(gap, 0, sizeof gap);
    gap[dep[t] = 0] = 1; q.emplace(t);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            if (dep[e[i].v] == -1 && !e[i].w) {
                gap[dep[e[i].v] = dep[u] + 1]++;
                q.emplace(e[i].v);
            }
        }
    }
}

void add(int u, int v, int w) {
    e[++cnt].nxt = head[u];
    head[u] = cnt; e[cnt].v = v, e[cnt].w = w;
}

int dfs(int u = s, int flow = 0x3f3f3f3f) {
    if (u == t) return flow;
    int rest = flow;
    for (int i = cur[u]; i; i = e[i].nxt) {
        cur[u] = i; 
        if (dep[e[i].v] + 1 == dep[u] && e[i].w) {
            int f = dfs(e[i].v, min(e[i].w, rest));
            rest -= f, e[i].w -= f, e[i ^ 1].w += f;
        }
        if (!rest) return flow;
    }
    if (!--gap[dep[u]++]) dep[s] = n + k + 2;
    gap[dep[u]]++;
    return flow - rest;
}

int ISAP() {
    bfs(); int res = 0;
    while (dep[s] < n + k + 2) {
        memcpy(cur, head, sizeof cur);
        res += dfs();
    }
    return res;
}

bool check() {
    cnt = 1; memset(head, 0, sizeof head);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (abs(a[i] - b[j]) + abs(b[j] - p) <= mid) {
                add(i, j + n, 1);
                add(j + n, i, 0);
            }
        }
    }
    s = n + k + 1, t = n + k + 2;
    for (int i = 1; i <= n; i++) add(s, i, 1), add(i, s, 0);
    for (int i = 1; i <= k; i++) add(i + n, t, 1), add(t, i + n, 0);
    return ISAP() == n;
}

再次优化-线段树优化建图

上述算法仍不能 AC。我们挖掘题目贪心性质。由于钥匙都在数轴上，所以在排序之后，一个人能取的钥匙一定是连续的。既然是向连续的点连边，我们就可以考虑用线段树优化建图。

大致思想是用像线段树一样的结构，建立起 \(k-1\) 个辅助节点，使得一个辅助节点在树上能与一个区间相连。这样，只要拆成 \(\log k\) 个区间（即和 \(\log k\) 个辅助节点连边）即可表示一个连续区间。

详细可以看洛谷日报。

现在 \(m = \mathcal{O}(n \log k)\)，总时间复杂度上界是 \(\mathcal{O}(\sqrt nm \log W)\)。

const int maxn = 6e3 + 5, maxm = 2e6 + 5;
int n, k;
long long p, mid;
long long a[maxn], b[maxn];

namespace ISAP {
    struct node { int v, w, nxt; } e[maxm];
    int head[maxn], cnt = 1, cur[maxn], dep[maxn], gap[maxn], cntu;
    int s, t;
    queue<int> q;
    void bfs() {
        memset(dep, -1, sizeof dep); memset(gap, 0, sizeof gap);
        gap[dep[t] = 0] = 1; q.emplace(t);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; i; i = e[i].nxt) {
                if (dep[e[i].v] == -1 && !e[i].w) {
                    gap[dep[e[i].v] = dep[u] + 1]++;
                    q.emplace(e[i].v);
                }
            }
        }
    }
    void add(int u, int v, int w) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].v = v, e[cnt].w = w; }
    int dfs(int u = s, int flow = 0x3f3f3f3f) {
        if (u == t) return flow;
        int rest = flow;
        for (int i = cur[u]; i; i = e[i].nxt) {
            cur[u] = i; 
            if (dep[e[i].v] + 1 == dep[u] && e[i].w) {
                int f = dfs(e[i].v, min(e[i].w, rest));
                rest -= f, e[i].w -= f, e[i ^ 1].w += f;
            }
            if (!rest) return flow;
        }
        if (!--gap[dep[u]++]) dep[s] = cntu;
        gap[dep[u]]++;
        return flow - rest;
    }
    int solve() {
        bfs(); int res = 0;
        while (dep[s] < cntu) {
            memcpy(cur, head, sizeof cur);
            res += dfs();
        }
        return res;
    }
}

namespace segment_tree {
    struct node; typedef node* pos;
    struct node { pos ls, rs; int l, r, u; node() { ls = rs = this; }};
    node buf[maxn], *root = buf, *buf_pos = buf;
    pos new_node(int l, int r) { pos p = ++buf_pos; p -> ls = p -> rs = buf; p -> l = l, p -> r = r; p -> u = ++ISAP::cntu; return p; }
    void build(pos p) {
        if (p -> l == p -> r) return ISAP::add(p -> u, ISAP::t, 1), ISAP::add(ISAP::t, p -> u, 0);
        int mid = (p -> l + p -> r) >> 1;
        p -> ls = new_node(p -> l, mid), build(p -> ls);
        p -> rs = new_node(mid + 1, p -> r), build(p -> rs);
        ISAP::add(p -> u, p -> ls -> u, 0x3f3f3f3f), ISAP::add(p -> ls -> u, p -> u, 0);
        ISAP::add(p -> u, p -> rs -> u, 0x3f3f3f3f), ISAP::add(p -> rs -> u, p -> u, 0);
    }
    void update(pos p, int id, int l, int r) {
        if (l <= p -> l && p -> r <= r) return ISAP::add(id, p -> u, 0x3f3f3f3f), ISAP::add(p -> u, id, 0);
        if (l <= p -> ls -> r) update(p -> ls, id, l, r);
        if (p -> rs -> l <= r) update(p -> rs, id, l, r);
    }
}


//记得对 b 排序
bool check() {
    ISAP::cnt = 1; segment_tree::buf_pos = segment_tree::buf;
    ISAP::s = n + 1, ISAP::t = n + 2, ISAP::cntu = n + 2;
    memset(ISAP::head, 0, sizeof ISAP::head);

    for (int i = 1; i <= n; i++) ISAP::add(ISAP::s, i, 1), ISAP::add(i, ISAP::s, 0);
    segment_tree::root = segment_tree::new_node(1, k);
    segment_tree::build(segment_tree::root);

    for (int i = 1; i <= n; i++) {
        int l = k + 1, r = 0;
        for (int j = 1; j <= k; j++) {
            if (abs(a[i] - b[j]) + abs(b[j] - p) <= mid) {
                l = min(l, j), r = max(r, j);
            }
        }
        if (l <= r) segment_tree::update(segment_tree::root, i, l, r);
    }
    return ISAP::solve() == n;
}