题解：P11502 [ROIR 2019] 配对 (Day 2)

· · 题解

题解何意？

实际上 b_t 就是 a_{i,t} 的中位数，我们只关心数与 b_t 的大小关系。设 a_{i,t}<b_t 为 0，> 为 1，= 为 2，那我们相当于要解决如下问题：

考虑最大流，直接暴力对 2\times 3^{k-1} 种串建图。发现保证了 a_{i,1} 互不相同，那么可以将所有串分为两部分，建成二分图。

以源点一侧为例，若当前这个串有 2，那么将最低的那个 2 替换成 0/1，连一条流量为 \inf 的边。否则，将这个串与对应的能匹配的串连边。汇点一侧同理。这样总边数为 \mathcal{O}(3^k)。用 Dinic 求解最大流即可做到 \mathcal{O}(27^k)，可以通过。当然可以像楼下说的那样用 HLPP 做到 \mathcal{O}(9^k\log n)，但是太没必要了。

对于构造方案，直接顺着流量推即可。

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int MAXN = 2e5 + 10;
const int MAXM = 5e3;
const int MAXK = 1460;
const int inf = 0x3f3f3f3f;

struct edge {
    int v, c, nxt;
    edge(int v = 0, int c = 0, int nxt = 0) : v(v), c(c), nxt(nxt) {}
} e[MAXM << 1]; int head[MAXK], tot = 1;

inline 
void add(int u, int v, int c) {
    e[++tot] = edge(v, c, head[u]), head[u] = tot;
    e[++tot] = edge(u, 0, head[v]), head[v] = tot;
}

int lst[MAXK], lvl[MAXK];

inline 
bool bfs(int s, int t) {
    memset(lvl, 0xff, sizeof lvl);
    queue<int> q; q.emplace(s), lvl[s] = 0;
    for (int u; !q.empty(); ) {
        u = q.front(), q.pop(), lst[u] = head[u];
        for (int _ = head[u]; _; _ = e[_].nxt) {
            int v = e[_].v, c = e[_].c;
            if (c && !~lvl[v]) lvl[v] = lvl[u] + 1, q.emplace(v);
        }
    }
    return ~lvl[t];
}

int dfs(int u, int t, int f = inf) {
    if (u == t) return f; int res = 0;
    for (int &_ = lst[u]; _; _ = e[_].nxt) {
        int v = e[_].v, c = e[_].c;
        if (!c || lvl[v] != lvl[u] + 1) continue;
        int x = dfs(v, t, min(f, c));
        e[_].c -= x, e[_ ^ 1].c += x, f -= x, res += x;
    }
    return res;
}

inline 
int dinic(int s, int t) {
    int res = 0;
    for (; bfs(s, t); res += dfs(s, t));
    return res;
}

int n, m, B, S, T, a[7][MAXN], b[7][MAXN];

vector<int> fs[729], ft[729];

int main() {
    scanf("%d%d", &n, &m), B = 1;
    for (int i = 1; i < m; i++) B *= 3;
    S = B << 1, T = S | 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) scanf("%d", &a[j][i]);
    }
    memcpy(b, a, sizeof a);
    for (int j = 0; j < m; j++) sort(b[j] + 1, b[j] + n + 1);
    for (int i = 1; i <= n; i++) {
        int k = n >> 1, x = 0;
        for (int j = 0; j < m; j++) {
            x *= 3;
            if (a[j][i] >= b[j][k + 1]) ++x, (a[j][i] <= b[j][k]) && ++x;
        }
        if (x < B) fs[x].emplace_back(i); else ft[x - B].emplace_back(i);
    }
    for (int i = 0; i < B; i++) {
        if (!fs[i].empty()) add(S, i, fs[i].size());
        if (!ft[i].empty()) add(B + i, T, ft[i].size());
        int p = 0;
        for (int j = 1, x = i; x; x /= 3, j *= 3) {
            if (x % 3 == 2) { p = j; break; }
        }
        if (p) {
            add(i, i - p, inf), add(B + i - p, B + i, inf);
            add(i, i - p - p, inf), add(B + i - p - p, B + i, inf);
        }
    }
    for (int i = 0; i < 1 << m - 1; i++) {
        int x = 0, y = 0;
        for (int j = m - 1; ~j; j--) x *= 3, y *= 3, (i >> j & 1) ? ++x : ++y;
        add(x, y, inf);
    }
    if (dinic(S, T) != n >> 1) return puts("NO"), 0; puts("YES");
    for (int i = B - 1; ~i; i--) {
        int p = 0;
        for (int j = 1, x = i; x; x /= 3, j *= 3) {
            if (x % 3 == 2) { p = j; break; }
        }
        if (!p) continue;
        for (int _ = head[i]; _; _ = e[_].nxt) {
            int v = e[_].v, c = e[_ ^ 1].c;
            if (v != i - p && v != i - p - p) continue;
            for (; c--; fs[v].emplace_back(fs[i].back()), fs[i].pop_back());
        }
        for (int _ = head[B + i]; _; _ = e[_].nxt) {
            int v = e[_].v - B, c = e[_].c;
            if (v != i - p && v != i - p - p) continue;
            for (; c--; ft[v].emplace_back(ft[i].back()), ft[i].pop_back());
        }
    }
    for (int i = 0; i < 1 << m - 1; i++) {
        int x = 0, y = 0;
        for (int j = m - 2; ~j; j--) x *= 3, y *= 3, (i >> j & 1) ? ++x : ++y;
        for (; !fs[x].empty() || !ft[y].empty(); ) {
            printf("%d %d\n", fs[x].back(), ft[y].back());
            fs[x].pop_back(), ft[y].pop_back();
        }
    }
}