拟阵学习笔记

C6H14 · 2022-08-06 12:10:03 · 个人记录

0.前言

dmy 讲课时讲了一个看起来很牛马牛逼的东西，但是他讲的太拉了我太菜了，所以去查了些资料才搞懂一点

然鹅……

所以我这个蓝名学这个干什么

由于我比较菜，可能写的会有一些错误的地方，望各位大佬指正

1. 拟阵概念

拟阵是一个很强大的模型，可以解决一大坨组合最优问题，学会了它你可以吊打 tourist

那么什么是拟阵呢？

假设我们现在有一个有限集 M，我们可以将它的所有子集和包含关系用一张 DAG 表示，其中每个点代表一个集合，每条边表示一个包含关系

为简化这个 DAG，我们忽略那些集合大小差大于 1 的包含关系与它们该连的边

比如有限集 \{ 1,2,3 \} 可以用下面这张图表示：

以后我们称两个集合一个比另一个大当且仅当它们的集合大小一个比另一个大

现在我们想选出其中几个子集，用它们组成一个新的集合 S（也叫 S 为 M 的子集族），S 必须满足下面两个性质：

• （遗传性）每个在 S 中的集合，它的所有子集都在 S 中（\forall A \in S,B \subset A,B \in A）

也就是在上面那张由 M 生成的 DAG 中，任选一个点 A 代表的集合加入到 S 中，必须同时将所有 A 能到达的点 B 代表的集合加入到 S 中

• （交换性）只要 A 包含的元素个数不是在 S 里的集合最大的，必定可以在 S 中找到一个恰好比 A 多一个元素的集合 B（\forall A,B \in S \land |A|<|B|,\exists a \in M,a \notin A,A \cup {a} \in S）

也就是将上面的 DAG 结点保留在 S 中集合代表的结点以及它们之间的边，按照代表集合大小排序后，除了在 S 中最大的那几个外，其他在 S 中的集合代表的结点入度必定不为 0

满足这两个性质的集合 S 与原来的集合 M 构成的二元组 (M,S) 就称为拟阵

这样我们可以把拟阵对应为原来那张 DAG 上的一个子图，满足所有源点代表集合大小相等且源点在原来的图上能到达的结点都在这个子图中

来个例子：

比如 S=\{ \{1,2\},\{2,3\},\{1\},\{2\},\{3\},\emptyset \}，(M,S) 就是拟阵，它满足上面的所有定义（不信你验证一下）

但是 S=\{ \{1,2\},\{2,3\},\{1\},\{2\},\emptyset \}，(M,S) 就不是拟阵，因为 \{ 2,3 \} 的子集 \{ 3 \} 并不在 S 中

再举个例子：

假设 M 为一张无向图上的边集，S 为其中不构成环的 M 的子集，(M,S) 也是一个拟阵，其中的极大独立集就是生成树

一个感性的理解：

我们随便取出一个不是生成树的边集，必定可以再找到一条边，连接两个连通块，这样的边肯定不构成环；随便选出一个不构成环的边集，随便删掉一条肯定也不会出现环

说到这你可能就发现了，有关生成树的最优化问题可以尝试转化为拟阵！

然鹅我们还不知道怎么求解有关拟阵的最优问题（我们甚至没定义拟阵上的最优概念），于是有了独立集的概念

2. 独立集与拟阵最优化问题

我们现在的目标是尝试将一些特殊的最优化问题转化为拟阵上的最优化问题并解决它

首先我们要对 M 中的每个元素分配一个权值 w_i ，这里 w_i \geqslant 0，并定义 S 中一个集合的权值为其中所有元素的权值和

这样拟阵上的最优化问题就可以转化找到为 S 中 \sum w_i 最大的集合

怎么找到这个集合呢？暴力

我们需要引入一个新的概念：独立集

只要集合 s 在拟阵的 S 中，我们就称 s 为独立集

你或许会想：这不新瓶装旧酒吗？你**骗我是吧

别急，还有其他概念：

• 若 \exists x \in M,x \notin A,A \cup \{x \} \in S，称 A 为可拓展的；否则称 A 为极大独立集

考虑 M 对应的 DAG，我们已经知道 S 可以对应一张子图，那么极大独立集就对应其中的源点，其他集合对应其他的点

还是拿 S=\{ \{1,2\},\{2,3\},\{1\},\{2\},\{3\},\emptyset \} 举例，\{1,2\} 和 \{2,3\} 就是极大独立集，其他集合都是可拓展的

显然同一拟阵中极大独立集的大小都相等

• 假如 A \in S 的权值是 S 中最大的，我们称 A 为权值极大独立集

显然权值极大独立集一定是极大独立集

求解权值极大独立集可以用贪心解决（虽说 dmy 讲课时说应该是贪心可以用权值极大独立集解决）：

1. 将 M 中的元素按照 w_i 从大到小排序

2. 维护权值极大独立集 I，初始化 I = \emptyset

3. 枚举 M 中元素 x，只要 \{ x \} \cup I 仍然为独立集就将 x 加入 I

上课写的狗屎板子：

void insert()
{
    sort(a+1,a+1+n,cmp);
    for (int i=n;i>=1;--i)
        if (check(a[i]))
        {
            add(a[i]);
        }
}

来个例题：求最小生成树权值和

直接让 M 为边集，S 为不构成环的边集的子集族，w_i 为边权大小相反数即可……吗？

要求 w_i \geqslant 0，还写个屁

那么我们让 w_i 为一个非常大的数减去边权行不行呢？

由于权值极大独立集元素个数是固定的（或者说边数是固定的），这样处理对答案的改变只与点数有关，所以是正确的！

别忙着发题解，你会发现这个算法已经有了个名字：Kruskal

是的，我们得到了一个新的 Kruskal 的证明方法

再来个例题：魔法商店

题意：给你 n 个 m 维向量，选第 i 个向量花费为 c_i，要求选出一个极大线性无关组，且花费最小（n,m \leqslant 500,c_i \leqslant 1000）

直接令 M= \{ z_i\}，S 为 M 中所有线性无关组的大集合，线性代数常识告诉我们这玩意满足遗传性和交换性，那么 (M,S) 是一个拟阵！

既然是个拟阵，就可以维护极大独立集了，这个比较简单，用类似线性基的方式将 z_i 高斯消元后逐个插入基中，插入前判断一下是不是线性无关的就行了，代码如下：

const long double eps=0.0001;
struct equip
{
    ll c;
    long double z[505];
    bool operator <(const equip &x) const
    {
        return c<x.c;
    }
} a[505];
bool check(equip );
void ins(equip );
ll n,ans,m,l;
bool here[505];
long double b[505][505],o=1.0;
int main()
{
    n=read(),m=read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            a[i].z[j]=read();
    for (int i=1;i<=n;++i)
        a[i].c=read();
    sort(a+1,a+1+n);
    ins(a[1]);
    ans+=a[1].c;
    for (int i=2;i<=n;++i)
    {
        if (check(a[i]))
            continue;
        ans+=a[i].c;
        ins(a[i]);
    }
    for (int i=1;i<=m;++i)
        if (here[i])
            ++l;
    write(l,' '),write(ans);
    return 0;
}
bool check(equip x)
{
    for (int i=1;i<=m;++i)
        if (fabs(x.z[i])>eps)
        {
            if (!here[i])
                return false;
            long double tmp=x.z[i]/b[i][i];
            x.z[i]=0;
            for (int j=i+1;j<=m;++j)
                x.z[j]-=tmp*b[i][j];
        }
    return true;
}
void ins(equip x)
{
    for (int i=1;i<=m;++i)
        if (fabs(x.z[i])>eps)
        {
            if (!here[i])
            {
                here[i]=1;
                for (int j=i;j<=m;++j)
                    b[i][j]=x.z[j];
                return;
            }
            long double tmp=x.z[i]/b[i][i];
            x.z[i]=0;
            for (int j=i+1;j<=m;++j)
                x.z[j]-=tmp*b[i][j];
        }
}

拟阵的功能远不止这些，在 2018 年国家集训队论文中杨乾澜大神介绍了拟阵的一个更牛马牛逼的扩展：拟阵交

3. 拟阵交

假设有两个拟阵 (M,S) 和 (M,T)，我们称它们的拟阵交为 S \cap T

有些问题要求最优化的答案有多个性质，只看单独某个性质都可以转为拟阵最优化问题，凑一坨却不好做

这时我们可以把每一个性质都抽象成一个拟阵，最后的答案即为拟阵交

然鹅大部分这样的问题都不好做，原因在于：

拟阵交不一定是拟阵

更令人悲观的是，大于等于三个拟阵交问题是 NP-Hard 的，可以规约到哈密顿路径

虽然但是，两个拟阵的交是有多项式算法的（怎么这么像 2-SAT 呢），我们下面就来介绍：

介绍一个新的图：交换图 G_{S,T}(I)，I 为某个集合

交换图是一个有向二分图，可以认为左部是 I 中的元素对应的点，右部是 \complement_M I

这个图的点为 M 中的元素

我们需要一个新的布尔数组 vis，用于记录 M 中的某个元素是否在左部

我们现在进行连边：

取出左部一个点 x 和右部一个点 y，记将 x 与 y 对调后左部为 I'，也就是 I'=(I-\{ x \}) \cup \{ y \}

• 若 I' \in S，连一条 x 到 y 的有向边，边权为 (-1)^{vis_i}w_y

• 若 I' \in T，连一条 y 到 x 的有向边，边权为 (-1)^{vis_i}w_x

再来张图，我们令 S=\{ \{1,2\},\{1 \},\{ 2 \},\emptyset \}，T=\{ \{2,3\},\{2 \},\{ 3 \},\emptyset \}，M = \{1,2,3\}，I=\{ 1,2\}，交换图就是：

现在我们来求拟阵交，使用增广法：

1. 初始化 I= \emptyset，并建立两个新结点 s,t

2. 建立交换图 G_{S,T}(I)

3. 找到右部所有加入 I 仍使 I \in S 的点，记作 X_1

4. 找到右部所有加入 I 仍使 I \in T 的点，记作 X_2

5. 将 s 与 X_1 的所有结点连一条边权为 0 有向边，X_2 的所有结点与 t 连一条边权为 0 的有向边

6. 求 s 到 t 的最短路，距离相同优先选择经过边数少的，可以用诈尸的 SPFA

7. 假如存在最短路，将这条最短路上的所有元素的 vis_i 变成 !vis_i，然后回到操作 2 循环

8. 假如不存在最短路，结束循环，I 即为所有 vis_i=1 的元素（除了 s,t 外）

好像复杂度不超过O(|I|^2n)？（毕竟我还在学习……）

5. 一些例子

例1：给你一个 n 个点 m 条边的无向图，再给你 n-1 个边集 A_1,A_2\ldots A_{n-1}，请构造一个方案，从每个边集选一条边后能凑出一个生成树，n,m \leqslant 200

令 S 为不构成环的边集族，T 为每个边集至多选一条边的边集族，感性理解 (E,S) 和 (E,T) 都是拟阵，求拟阵交就行

例2：CF1556H

给你一个 n 个点的无向完全图，边权给定，求前 k 个点中第 i 个点的度数不超过 d_i 的最小生成树的边权和，n \leqslant 50，k \leqslant 5

这个题复杂一点：

首先，S 显然是不构成环的边集组成的拟阵

那么 T 是什么呢？

如果你想将前 k 个点都满足限制当做 T，你就 gg 了

考虑这样一个情况（度数限制为 1）：

这个情况中，T 应该是 \{ \{(1,2),(3,4)\},\{(1,2)\},\{(2,3)\},\{(3,4)\},\emptyset \}