【学习笔记】拟阵

对于这一类问题，有统一的解决方法，即 按照权值从大到小贪心 ，直到不能选为止。

常见的拟阵模型：

• 物品有 $(v_i,w_i)$ 两个属性，选出一个集合 $S$ ，求 $\max ({\sum }_{i\in S}{v}_i)$ ，其中 $S$ 的任意非空子集属性异或和 $\ne 0$ 。

M(E,I) 中 E 表示 n 个物品组成的集合， I 表示满足任意非空子集属性和 $\ne 0$ 的物品集合。

• MST 。

M(E,I) 中 E 表示边的集合， I 表示满足没有环的边的集合。

因为求的是 MST ，所以考虑 $w(u,v)=w_0-w(u,v)$ ，注意我们求的必须是一个生成树，所以需要避免边的权值为负 。（否则可以选择不选）。

• 最小基环生成树 。

证明略。同样是按边排序贪心，证明可以反证（拟阵的证明过程比较麻烦）。

• 有 $n$ 个向量 $(a_1,a_2,..,a_m)$ ，每个向量有权值 $va{l}_i$ ，选出线性无关的向量集合 S ，在满足 |S| 最大的前提下求 $\min ({\sum }_{i\in S}va{l}_i)$ 。

这题可以转化为求 $\max ({\sum }_{i\in S}va{l}_i)$ ，因为权值为正，所以 S 一定是原拟阵的基，又因为拟阵的基大小相同（否则与交换性矛盾），所以直接把 $va{l}_i$ 从小到大排序贪心即可。