本文参考2018集训队论文《浅谈拟阵的一些拓展及其应用》
本文只有结论无证明，证明参考《浅谈拟阵的一些拓展及其应用》。
定义
对于一个集合 S {S} S，如果 S S S的子集 T T T满足某种特殊性质，则将 T T T称为独立集，特别地，将空集称为独立集。
定义拟阵 M = ( S , I ) M=(S,I) M=(S,I)表示，其中 I I I为所有独立集的集合，并且 I I I需要满足两个性质才能被称为拟阵：
- 遗传性：如果 T ∈ I T\in I T∈I，则任意 T {T} T的子集 P P P都要满足 P ∈ I P\in I P∈I。
- 交换性：如果 A , B ∈ I A,B\in I A,B∈I， ∣ A ∣ < ∣ B ∣ |A|<|B| ∣A∣<∣B∣，则存在 x ∈ B / A x\in B/A x∈B/A使得 A + { x } ∈ I A+\{x\}\in I A+{x}∈I。
只要定义的独立集满足拟阵的性质就可以用以下拟阵算法。
最大权独立集
对于拟阵
M
=
(
S
,
I
)
M=(S,I)
M=(S,I)，设
S
=
{
s
1
,
s
2
,
.
.
.
,
s
n
}
{S=\{s_1,s_2,...,s_n\}}
S={s1,s2,...,sn}，每个元素
s
i
{s_i}
si都有一个权值
w
(
s
i
)
{w(s_i)}
w(si)，求一个最大的
T
∈
I
{T\in I}
T∈I，使得
∑
e
∈
T
w
(
e
)
\sum\limits_{e\in T}w(e)
e∈T∑w(e)最大化。
贪心算法：
按
w
(
s
i
)
{w(s_i)}
w(si)从大到小将点集排序，设排序后的点集为
{
e
1
,
e
2
,
.
.
.
,
e
n
}
\{e_1,e_2,...,e_n\}
{e1,e2,...,en}，设最开始
T
=
∅
T=\varnothing
T=∅。
依次遍历
{
e
1
,
e
2
,
.
.
.
,
e
n
}
\{e_1,e_2,...,e_n\}
{e1,e2,...,en}，遍历到
e
i
{e_i}
ei时，如果
T
+
{
e
i
}
{T+\{e_i\}}
T+{ei}是独立集，则将
{
e
i
}
\{e_i\}
{ei}加入到集合
T
{T}
T。
典型的例子是
k
r
u
s
k
a
l
kruskal
kruskal求最小生成树。
拟阵交
对于两个拟阵
M
1
=
(
S
,
I
1
)
,
M
2
=
(
S
,
I
2
)
M_1=({S,I_1}),M_2=(S,I_2)
M1=(S,I1),M2=(S,I2)，求一个
I
∈
I
1
∩
I
2
{I\in I_1\cap I_2}
I∈I1∩I2。
求交算法：
令初始
I
=
∅
{I=\varnothing}
I=∅。
- 对 I {I} I建二分图，如果 x ∈ T , y ∈ S / T x\in T,y\in S/T x∈T,y∈S/T满足 T − { x } + { y } ∈ I 1 T-\{x\}+\{y\}\in I_1 T−{x}+{y}∈I1，则建立 x → y x\to y x→y的有向边。如果 x ∈ T , y ∈ S / T x\in T,y\in S/T x∈T,y∈S/T满足 T − { x } + { y } ∈ I 2 T-\{x\}+\{y\}\in I_2 T−{x}+{y}∈I2，则建立 y → x y\to x y→x的有向边。
- 定义 X 1 = { x ∈ S / I : I + { x } ∈ I 1 } , X 2 = { x ∈ S / I : I + { x } ∈ I 2 } X_1=\{x\in S/I: I+\{x\}\in I_1\},X_2=\{x\in S/I: I+\{x\}\in I_2\} X1={x∈S/I:I+{x}∈I1},X2={x∈S/I:I+{x}∈I2}。找一条从 X 1 {X_1} X1任意一点到 X 2 {X_2} X2任意一点的最短路径，令路径上的点集为 P P P，让 I = ( I ∪ P ) − ( I ∩ P ) {I=(I\cup P)-(I\cap P)} I=(I∪P)−(I∩P)。
1 , 2 1,2 1,2的过程成为一次增广，重复增广过程直到找不到路径，就找到了最大的 I I I
最大带权拟阵交
如果每个点
s
1
∈
S
s_1\in S
s1∈S带有点权
w
(
s
1
)
w(s_1)
w(s1)，在建图时如果
x
∈
I
x\in I
x∈I,则其权值设为
−
w
(
x
)
-w(x)
−w(x)，如果
x
∈
S
/
I
x\in S/I
x∈S/I，则权值设为
w
(
x
)
w(x)
w(x)。
找最短路时以权值最小为第一关键字，路径长度最小为第二关键字。
这里找最大带权在最短路里却以权值最小为关键字基于最小最大定理，不要觉得奇怪。