Note -「Matroid Union」

cirnovsky /

拟阵 M=(S,I)M=(S,I),其中 SS 是事件的集合,IISS 的子集的集合,满足一定的限制条件。拟阵有如下的定义(性质):

  • 遗传性:若 AIA\in I,则 AA,AI\forall A^*\subseteq A,A^*\in I
  • 交换性:A,BI,A<B\forall A,B\in I,|A|<|B|,有 xBA\exists x\in B\setminus A,使得 A{x}IA\cup\{x\}\in I

有这样一类问题,让你选择一个 II 的子集 II^*,使得 xIf(x)\sum_{x\in I^*}f(x) 最大,其中 f(x)f(x) 是一个,一个一个一个一个。