还是过来学这个了（
参考文献有，wiki上的若干词条，18年杨乾澜的集训队论文 浅谈拟阵的一些拓展及其应用，15年wc董宏华的课件 拟阵选讲，zghtyarecrenj的谷日报 从拟阵基础到 Shannon 开关游戏，21年潘佳奇的集训队论文 浅谈线性代数与图论的关系。如果你很有兴趣，可以看看Tutte的 Lectures on Matroids，反正我是懒得看了（
拟阵
一个子集系统包含一个ground set \(E\) 和一个ground set的子集的集合\(\mathcal I\)。
一个拟阵是一个子集系统，其中\(\mathcal I\)中的集合称为 独立集，并且有以下三个限制 :
-
空集必须是独立集。
-
独立集的子集还是独立集。
-
(independent set exchange property 独立集交换性质)如果有\(A,B\)两个独立集，并且\(A\)比\(B\)更大，那么一定存在一个元素\(x\in A\setminus B\)使得\(B+x\)也是独立集。
第三个性质看起来非常有用。
在提到拟阵的大小时(比如分析复杂度时)，默认\(m=\vert E\vert\)。
两个简单拟阵
均匀拟阵\(U_n^k\) : 一个集合独立当且仅当大小\(\leq k\)。
环拟阵 : 无向图，ground set是边集，一个集合独立当且仅当无环。
考虑证明它的交换性质。考虑现在有两个集合\(A,B\)且\(\vert A\vert>\vert B\vert\)，那么\(A\)中必然存在一个连通块，其中的点在\(B\)中属于至少两个不同的连通块，在\(B\)中加入\(A\)中这两个连通块之间的边即可。
注意有向图无环不是拟阵。
基
最大独立集称为基。根据交换性质，我们知道极大独立集就是最大独立集。
一个拟阵可以被它的所有基表示出来，因为一个拟阵的所有独立集就是基们的所有子集。
strong basis exchange lemma 强基交换定理 如果有两个基\(A,B\)，以及一个元素\(a\in A\setminus B\)，则必然存在一个元素\(b\in B\setminus A\)使得\(A-a+b\)，\(B-b+a\)都是基。
这个结论很有用，但是我看起来不会用到它，因为不会写证明（
环
一个集合是环，当且仅当它不是独立集，并且它删掉任何一个元素之后都是独立集。
环的大小不是唯一的。一个简单的结论是，没有一个环包含另一个。
结论 基加入一个元素之后，必然包含恰好一个环。
一个拟阵不能由它的所有环表示出来，比如森林的环拟阵没有环。
秩
定义一个集合\(S\)的秩\(r(S)\)是它里面最大独立集的大小。
秩函数满足三条性质。
-
\(0\leq r(S)\leq \vert S\vert\)。
-
对于\(A\subseteq B\)，\(r(A)\leq r(B)\)。
-
对于任意\(A,B\)，\(r(A\cup B)+r(A\cap B)\leq r(A)+r(B)\)。这个被称为 次模性，可以理解为定义在子集上的函数的上凸性。
结论 如果一个ground set的子集上的秩函数满足这三条性质，那么它们(ground set和秩函数)就定义了一个拟阵，其中一个集合是独立集当且仅当它的秩等于它的大小。
秩函数被广泛运用于关于拟阵的证明，因为它以代数方法描述了拟阵的结构。但是我啥证明也不会，所以不会怎么用到这个东西（
直和
两个拟阵的ground set不交的情况下，可以直接把它们合并，此时独立集取两边的笛卡尔积，这个称为直和。显然拟阵的直和还是拟阵。
另外几个拟阵
liner matroid 线性拟阵(vector matroid 向量拟阵，liner algebra matroid 线代拟阵) : 元素是向量，独立集定义为不线性相关。
colorful matroid 有色拟阵 : 每个元素有一个颜色，独立集定义为颜色互不相同。
划分拟阵 : 每个元素有一个颜色，每个颜色有一个选择的个数上限，独立集定义为满足所有这些限制的。划分拟阵是若干均匀拟阵的直和。当这些限制都是\(\leq 1\)的时候，划分拟阵特化为有色拟阵。
表示
如果一个拟阵同构于一个某个域上的线性拟阵，那么说它在这个域上被这个线性拟阵表示了。
环拟阵在任意域上是可表示的，做法是每个点分配一个位置，每条边的向量在一个端点上是\(1\)，另一个是\(-1\)，这样通过调整边的符号，环总是线性相关的。在任意域上可表示的拟阵称为正则拟阵，在\(GF(2)\)上可表示的拟阵称为二元拟阵。
结论 正则拟阵必然可以同构于一个全幺模矩阵的各列组成的线性拟阵。
结论 如果一个拟阵在\(GF(2)\)和\(GF(3)\)上都可表示，那么它是正则的。
关于正则拟阵，一个牛逼结论是，可以用类似于基尔霍夫矩阵的做法来做基计数。具体可以在 Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs 看到。可惜的是正则拟阵实在是很少，我们常见的就只有环拟阵了。
也有说法是线性拟阵指的是可表示拟阵，而那个向量组成的拟阵应该叫向量拟阵。
显然线性拟阵并不一定是正则拟阵。比如我在看到这个的时候，立马就想到可以做刚性拟阵的基计数，然后就会很好玩了，但是实际上完全做不了。任意域上线性拟阵的基计数可以归约二分图最大匹配计数，使用后面会提到的匹配拟阵。
贪心
ground set里面的每个元素有一个权值，要找到权值和最大的基。
做法是按权值从大到小排序，依次尝试加入。
结论 如果一个不一定是拟阵的东西满足拟阵的前两条限制，并且这个贪心在它上面总是正确的，那么它必然确实是一个拟阵。
随便切一个
cqoi2013 新nim游戏
两个人在玩nim游戏，但是规则不是很一样 : 第一轮先手可以选择若干堆直接拿空，也可以一堆不选；第二轮后手是一样的，接下来游戏按照一般的nim游戏进行。求先手是否必胜，如果必胜的话求第一轮拿的总石子数的最小值。\(n\leq 100,a_i\leq 10^9\)。
先手输了当且仅当剩下的xor和为\(0\)，那么先手的目标就是让剩下的没有任何子集的xor和为\(0\)，也就是剩下的不线性相关。问题变成选择一个权值最大的极大线性无关子集，贪心即可，一边贪心一边维护一个线性基来判断是否线性相关。
对偶拟阵
一个拟阵\(M\)的对偶拟阵\(M^\ast\)定义为，保留\(M\)的ground set不变，把\(M\)的基全部取补。
环拟阵的对偶拟阵称为bond matroid 键拟阵(余环拟阵)，但是由于bond是极小割，所以我接下来把它称为 极小割拟阵。极小割拟阵中，一个集合独立当且仅当集合外的边可以使图连通，或者说它描述了 删一些边使图仍然连通 这样的东西。极小割拟阵中的环是所有的极小割，这也是它名字的由来，键拟阵是直译，余环拟阵则是因为它和环拟阵的对偶性。
均匀拟阵的对偶还是均匀拟阵。
群联拟阵
匹配拟阵 : 对于一个二分图，匹配拟阵的ground set是所有右部点，一个集合独立当且仅当它到左部点有完美匹配。
bicircular matroid，试译为 基环树拟阵 : 无向图，ground set是所有边，一个集合独立当且仅当是基环树森林，这里认为树也是基环树。是匹配拟阵的特例，具体一点就是它所同构的匹配拟阵的二分图是 左部点是图中的点而右部点是边。
群联拟阵(gammoid) : 有向图，有一些点是起点，另一些点是终点。群联拟阵的ground set是所有终点，一个集合独立当且仅当存在若干个起点到这个集合的一组点不交路径。匹配拟阵是群联拟阵的特例。
严格群联拟阵 : 群联拟阵，并且所有点都是终点。每个匹配拟阵都和一个严格群联拟阵对偶，反之亦然。
删除和收缩
拟阵\(M\)删除和收缩集合\(T\)是拟阵\(M\)和它的ground set的一个子集\(T\)的运算，记为\(M\vert T,M\setminus T\)，运算的结果是一个新的拟阵。
在一个拟阵中删除一个集合\(T\)，就是直接删掉了。在环拟阵上，这对应于删掉\(T\)中的边。
在一个拟阵中收缩一个集合\(T\)，ground set会减去\(T\)，同时新拟阵的独立集定义为并上\(T\)后在原拟阵中独立的集合。在环拟阵上，这对应于缩\(T\)中边的端点。
如果你想在拟阵中钦点选择一些元素，而不从ground set中删掉它们，这是不可能的!因为此时空集变得不再合法，这就不是拟阵了。
但是如果你想在拟阵中不考虑一些元素，也就是包含这些的都不是独立集了，而不从ground set中删掉它们，是没有问题的。
拟阵交
对于两个ground set相同的拟阵，定义它们的交中一个集合独立，当且仅当它在两个拟阵中都独立。
通常说的拟阵交算法用来求解两个拟阵交中的最大独立集，带权拟阵交用来求解最大权独立集。
截断
任意拟阵和均匀拟阵的交还是拟阵。交上一个均匀拟阵的操作被称为截断。
拟阵交算法
求解两个拟阵的最大公共独立集。
现在有两个ground set都是\(E\)的拟阵\(M_1,M_2\)，并且有一个独立集\(I\)，定义关于\(I\)的交换图\(D_{M_1,M_2}(I)\)为一个二分图，左部点是\(I\)而右部点是\(E\setminus I\)，并且如果对于\(x\in I,y\in E\setminus I\)，如果\(I-x+y\)在\(M_1\)中独立，则连边\(x\rightarrow y\)；如果\(I-x+y\)在\(M_2\)中独立，则连边\(y\rightarrow x\)。
定义集合\(X_1\)为所有\(x\in E\setminus I\)使得\(I+x\)在\(M_1\)中独立，\(X_2\)为使得那个在\(M_2\)中独立的。
我们从\(I=\varnothing\)开始，进行若干轮增广，每次增广建立交换图并在上面求出\(X_1\)到\(X_2\)的最短路，和\(I\)取对称差，直到不存在路径为止。容易发现每一轮增广后\(I\)的大小会增加\(1\)。证明没有/cy
考虑最小权公共独立集，设权值是\(w\)，我们给\(I\)中每个元素\(x\)赋点权\(-w(x)\)，而给\(E\setminus I\)中每个元素\(x\)赋点权\(w(x)\)，按点权为第一关键字，路径长度为第二关键字跑最短路即可。可以证明交换图上没有负环。
判断独立性
注意到在拟阵交算法中，我们需要支持，有一个集合，若干次判断它加入一个元素之后，或者删除一个元素再加入一个元素之后是否是独立的，询问之间是独立的，设答案的大小是\(r\)，则一共有看起来\(O(r^2)\)次删除和\(O(r^2m)\)次询问。
对于均匀拟阵，可以用来水字数。
对于划分拟阵，直接开个桶。
对于图拟阵，这个可以直接跑出删掉每个元素之后的并查集，我们需要跑\(O(r^2)\)个并查集，每个是\(O(m)\)的，看起来并不会提高复杂度。如果你在做带权拟阵交，那么好消息是，不用优化了!因为每轮spfa一次本身已经是\(O(rm^3)\)，而我们只有\(O(r^2m)\)次询问，每次\(O(m)\)跑就行了。
对于极小割拟阵，把它反过来就行了。但是这个在\(r\)很小的时候就输了，是\(O(rm^2)\)的。不过谁会卡这个（
对于线性拟阵，设向量长度是\(l\)，直接删掉每个元素跑高消得到一个对角基，复杂度是\(O(r^2l^3)\)，每次查询是\(O(l^2)\)，总共是\(O(r^2l^3+r^2ml^2)\)。前者一般情况下已经不是瓶颈，但还可以优化，可以对所有元素跑一个对角基，然后考虑基外的元素可以替换哪些基内的元素，看起来如果它真了，复杂度会降为\(O(r^2ml^2)\)。
对于匹配拟阵，可以网络流直接实现加入删除。看起来并不简单，复杂度也很玄学。在某些情况下也许可以使用hall定理。但是反正拟阵交很慢，不会有出题人继续要求这方面优化吧（
线性拟阵交
对于两个线性拟阵，有一个牛逼方法可以给它们求交。我们把每个向量乘上一个(不同的)随机值，然后随机排列成两个矩阵\(A,B\)，答案就是\(AB^T\)的秩。
线性拟阵奇偶问题
给一些向量对$(x_i,y_i)$，你要选出尽可能多使得它们放在一起线性无关。
取一组随机值$r$，求$\sum r_i(x_iy_i^T-y_ix_i^T)$的秩。
可以看到这个问题比拟阵交强。
它的加权版本是能做但很复杂的。在任意拟阵上显然是npc的。
随便切几个
下面是一些简单的拟阵交问题。
二分图最大权匹配
没有一个左部点连两条边，没有一个右部点连两条边，是左右两个有色拟阵的交。
最小外向树
把图当成无向图时无环，并且每个点入度不超过\(1\)，而根的入度不超过\(0\)，是图拟阵和划分拟阵的交。
Colourful tree
图，每条边还有一个颜色，求所有边颜色互不相同的mst。
有色拟阵和图拟阵的交。
CF1284G Seollal
棋盘，一些格子没了，求四连通意义下的一棵生成树，满足黑白染色后所有的叶子和\((1,1)\)不同色，或判定为无解。\(n,m\leq 20\)。
考虑这相当于限制了黑点都不能是叶子，也就是黑点的度数\(\geq 2\)，这等价于黑点没有邻边的方向数量\(\leq 2\)。于是我们考虑限制不在我们选的生成树里的边，然后这就是一个划分拟阵和一个极小割拟阵的交。这个做法也在题解的讨论区被Hazyknight指出了。
另一个想法是拟阵交会最大化边数，这使得黑点更有可能连超过一条边，但是如果有的点连了很多就会占用很多边导致剩下的点没边了，于是我们限制每个黑点度数不超过\(2\)，和环拟阵求交得到一个森林，如果此时每个黑点度数都是\(2\)那么可以直接不停加边把它变成树，否则必然无解。
SWERC11 B. Coin Collecting
有\(n\)对信封，每个信封里面有两个不同种的硬币，你可以在每一对里选择最多一个，要求你选择的信封集合不存在一个非空子集使得每种硬币出现偶数次，求最多可以选多少硬币。
每个信封是一条边，然后就是一个有色拟阵和图拟阵的交。
可能那时候拟阵交还不是很普及，所以wc14的课件中提到出题人认为这个题是”very hard(I mean, impossible)”/jy，也许是因为出题人独立发现了拟阵交算法。
North American Invitational Programming Contest 2018 G. Rainbow Graph
带权无向图，每条边有红绿蓝之一的颜色。对每个\(k=1,...,m\)求出选\(k\)条边并使得忽略红色边的图和忽略蓝色边的图都连通的最小权值和，如果不存在这样的方案则输出\(-1\)。\(n,m\leq 100\)。
使图连通显然要用极小割拟阵，然后就是两个极小割拟阵的交，具体一点就是第一个拟阵中，删的边之外的蓝绿边使图连通则独立，这是 选的边中蓝绿边使图无环则独立 的拟阵的对偶，请注意这里红边都是计入集合大小的，对于某些不计入的问题拟阵难以描述；第二个同理。注意到拟阵交算法在跑的过程中每一步都是最优的，所以只需要跑一遍，这跟跑费用流的时候求每个流量的费用是一样的。
这个题可以在qoj和baekjoon提交。
Shannon开关游戏
有一个无向图，A和B两个人轮流操作，A每次选择一条边删掉，B每次选择一条边固定使得A不能删它，如果最后\(u,v\)两个点连通则B获胜，否则A获胜。求这个游戏是A必胜，B必胜还是先手必胜(显然不可能后手必胜)。
往\(u,v\)上加一条边，那么问题变成获得一个包含这条边的环。
结论是，如果存在两棵不交的生成树，那么不管\(u,v\)是啥，都是B必胜，否则A先手必胜，而B先手不清楚。可以用强基交换定理证明这样做的正确性，大概是B维护两个基，而A如果破坏了一个，B就找到可以换过去的那条边，把它固定住。
那么如何判定是否存在两棵不交的生成树呢/yun，考虑我们找到一棵生成树使得剩下的边还有一棵生成树，这就是这个图的环拟阵和它的极小割拟阵的交。
放一份Rainbow Graph的代码。其中Matroid类用于判定独立性。感觉实际上还是挺简洁的，不比费用流难写。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<stdio.h>
#include<string.h>
#include<vector>
using std::vector;
int n,m;
const int N=102,M=104;
struct Edge{ int u,v,w;char type; }a[M];
bool I[M];
struct Matroid
{
char ban;
inline Matroid(char _ban):ban(_ban){}
int f[N];
inline void clear(int n){ for(int i=1;i<=n;i++) f[i]=i; }
int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
inline void merge(int x,int y){ f[find(x)]=find(y); }
inline bool check(int x,int y)
{
I[x]=0,I[y]=1;
clear(n);
int cnt=n;
for(int i=1;i<=m;i++) if(!I[i]&&a[i].type!=ban&&find(a[i].u)!=find(a[i].v)) merge(a[i].u,a[i].v),cnt--;
I[x]=1,I[y]=0;
return cnt==1;
}
}M1('R'),M2('B');
vector<int> e[M];
int w[M],pre[M];
int dis[M],len[M];
struct Queue{ int head,tail,q[M*M]; inline void clear(){ head=1,tail=0; } inline void push(int x){ q[++tail]=x; } inline void pop(){ head++; } inline int front(){ return q[head]; } inline bool empty(){ return head>tail; } }q;
bool inque[M];
inline void spfa(int s)
{
memset(pre,0,sizeof(pre)),memset(dis,0x3f,sizeof(dis)),memset(len,0,sizeof(len));
q.clear(),q.push(s);
dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
inque[u]=0;
for(int v:e[u])
if(dis[u]+w[v]<dis[v]||(dis[u]+w[v]==dis[v]&&len[u]+1<len[v]))
dis[v]=dis[u]+w[v],len[v]=len[u]+1,pre[v]=u,inque[v]?0:(q.push(v),inque[v]=1);
}
}
inline bool argument(int &ans)
{
int s=m+1,t=m+2;
for(int i=1;i<=m+2;i++) e[i].clear();
for(int i=1;i<=m;i++) if(I[i])
for(int j=1;j<=m;j++) if(!I[j])
M1.check(i,j)?e[i].push_back(j):(void)0,M2.check(i,j)?e[j].push_back(i):(void)0;
for(int i=1;i<=m;i++) if(!I[i])
M1.check(0,i)?e[s].push_back(i):(void)0,M2.check(0,i)?e[i].push_back(t):(void)0;
for(int i=1;i<=m;i++) w[i]=(I[i]?a[i].w:-a[i].w);
spfa(s);
if(!pre[t]) return 0;
for(int u=pre[t];u!=s;u=pre[u]) I[u]^=1,ans+=w[u];
return 1;
}
int _ans[M];
int main()
{
scanf("%d%d",&n,&m);
int ans=0;
for(int i=1;i<=m;i++) scanf("%d%d%d %c",&a[i].u,&a[i].v,&a[i].w,&a[i].type),ans+=a[i].w;
for(int i=m;i>=1;i--)
{
_ans[i]=ans;
if(ans!=-1&&!argument(ans)) ans=-1;
}
for(int i=1;i<=m;i++) printf("%d\n",_ans[i]);
return 0;
}
拟阵并
定义\(k\)个拟阵的并是一个拟阵，它的ground set是各拟阵ground set的并，而一个集合是独立的当且仅当存在一种方案把它划分成\(k\)个子集，使得第\(i\)个子集在第\(i\)个拟阵中是独立的。
定理 拟阵并确实是拟阵。
拟阵划分
拟阵划分解决若干个拟阵的并中的独立性判定。
拟阵划分是一个增量算法，也就是如果已知\(I\)的划分方案\(I_1,I_2,...\)，可以计算\(I+x\)的划分方案。
类似于拟阵交，我们定义拟阵\(M_i\)上独立集\(I_i\)的交换图\(D_{M_i}(I_i)\)是一个有向二分图，左部点是\(I_i\)而右部点是\(E_i\setminus I_i\)，如果\(I_i-x+y\)是独立集，则连边\(x\rightarrow y\)。定义\(F_i\)为所有满足\(I_i+x\)仍然独立的元素\(x\)。把每个拟阵的交换图和\(F_i\)并起来，得到总的交换图和集合\(F\)。
结论 如果\(I\)是独立集，那么\(I+x\)是独立集，当且仅当交换图中\(F\)可以到达\(x\)。
然后我们每次找到\(F\)到\(x\)的最短路，每经过一条边就进行一个替换就行了，我没写过所以并不了解细节。
自己并自己
对于拟阵自己并自己若干次的情况，有一个关于秩函数的牛逼结论，但是我不懂。可能会来补（
结论 一张图可以被不超过\(k\)个生成树覆盖，当且仅当对于任意点集\(S\)，都有\(\vert E(S)\vert\leq k(\vert S\vert-1)\)，其中\(E(S)\)表示\(S\)的导出子图的边集。
于是可以二分之后使用最大权闭合子图计算图的最小生成树覆盖。应该吧（