「Luogu 4934」礼物 (Dilworth定理 + 拓扑排序DAG求最长链 + 连边优化)

发表于 | | + s

4934 礼物
题意：$n$个$[0,2^k)$的数，分最少的组使得对于每个组的任意$a_1,a_2$, $a_1 \text{and} a_2 < \min(a_i,a_2)$，输出最少分组和一组方案。

首先将$a_1 \text{and} a_2 < \min(a_i,a_2)$转化，我们发现$a_1 \text{and} a_2$是不可能大于$\min(a_i,a_2)$的，所以这里就相当于只有等于的情况不成立。进一步分析可得，对于每个组的任意$a_1,a_2$，都不存在$a_1 \subseteq a_2$。

先介绍偏序：

偏序的定义
设$R$是集合$A$上的一个二元关系，若R满足：
1、自反性：对任意$x∈A$，有$xRx$；
2、反对称性（即反对称关系）：对任意$x,y∈A$，若$xRy$，且$yRx$，则$x=y$；
3、传递性：对任意$x, y,z∈A$，若$xRy$，且$yRz$，则$xRz$。
则称$R$为$A$上的偏序关系。
符号$≤$

具有偏序关系的集合$P$为偏序集，对应一个DAG图

严格偏序的定义
1、非自反性：$x ≮ x$
2、非对称性：若$x < y$, 则$y ≮ x$
3、传递性：若$x < y, y < z$, 则$x < y$

严格偏序也对应一个DAG图。但是不能使用Dilworth定理

Dilworth定理
在DAG图中
1、最小反链覆盖等于最长链长度等于拓扑序层次数：拓扑排序
2、最小链覆盖等于最长反链长度等于链的起点数：二分图
反链：在DAG图中不存在任意两个点是前驱后继关系的点集

将$a \subseteq b$看作一个偏序关系(题目保证$a_i$互不相同，则为集合)，然后建立一个 DAG 图，根据Dilworth定理，我们可以发现这里就是在求一个最小反链覆盖，那么求图的最长链即为答案。

注意本题的连边优化，若$u$到$v$有一条边，$v$到$w$有一条边，那么$u$到$w$的边是无意义的。所以我们每次连边只用连与当前状态二进制下1相差一位的。因为这样连就不会连出上面的$u$到$w$的边，并且将边的数量转到了$k \cdot 2^n$级别。

知识点：
1、Dilworth定理、偏序

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

namespace flyinthesky {

    const int MAXN = 1100000 + 5;

    int n, k, vd[MAXN], dp[MAXN], ino[MAXN];
    vector<int > G[MAXN], vec[MAXN];
    queue<int > q;

    void clean() {
        ms(vd, 0), ms(dp, 0), ms(ino, 0);
    }
    int solve() {

        clean();
        cin >> n >> k;
        for (int x, i = 1; i <= n; ++i) scanf("%d", &x), vd[x] = 1;
        for (int S = 0; S < (1 << k); ++S) 
        for (int i = 0; i < k; ++i) if ((S & (1 << i)) == 0) G[S].push_back(S ^ (1 << i)), ++ino[S ^ (1 << i)];

        q.push(0);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (vd[u]) ++dp[u];
            for (int i = 0; i < (int)G[u].size(); ++i) {
                int v = G[u][i];
                ino[v]--;
                dp[v] = max(dp[v], dp[u]);
                if (ino[v] == 0) q.push(v);
            }
        }

        for (int u = 0; u < (1 << k); ++u) {
            if (!vd[u]) continue ;
            vec[dp[u]].push_back(u);
        }

        int sz = 0;
        for (int i = 0; i <= dp[(1 << k) - 1]; ++i) if ((int)vec[i].size() > 0) ++sz;
        printf("1\n%d\n", sz);

        for (int u = 0; u <= dp[(1 << k) - 1]; ++u) {
            if ((int)vec[u].size() <= 0) continue ;
            printf("%d ", (int)vec[u].size());
            for (int i = 0; i < (int)vec[u].size(); ++i)
                printf("%d ", vec[u][i]);
            printf("\n");
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------