拟阵
(latest updated on 2020-08-10)
大量基础定义警告，参考了wiki和2018论文《浅谈拟阵的一些拓展及其应用》，如果想看大段详细证明请移步论文
拟阵的概念比较抽象，有多种定义方法，结合这些定义方法可以更具体地了解拟阵的基础性质
前言
很多问题可以转化为拟阵，但是并不是所有问题都可以通过简单的拟阵操作得到答案
在具体问题中，很多时候有着更优的算法解决拟阵运算无法解决的操作
但是对于一个奇怪的问题，如果转化为类似拟阵的操作后，就有很多性质可以拿过来套
拟阵的应用，更多还是用 诸多的性质 把复杂,抽象问题向更简单的方向转化(便于乱搞)
也可以便于简化问题的证明，所以这个东西了解一下也差不多了
(不会有人丧心病狂到专门出一个拟阵交的题吧)
符号及约定
(|S|)集合大小
(S-T)，删除(S)中在(T)中的元素
(aRightarrow b)若(a)则(b)
(aLeftrightarrow b)，(a,b)等价
(ain b)元素(a)是集合(b)中的一个元素
(asube b)，集合(a)是集合(b)的子集
(exists) 存在
(forall) 任意
幂集
一个集合(S)的所有(2^{|S|})个子集构成的集合是(S)的幂即(P(S))或者(2^S)
集族
给定集合(S) 的一些子集构成的类(F)叫做(S)的子集族（或称S 上的集合族）,(F sube 2^S)
用独立集定义拟阵(似乎是最直观的定义)
一个二元组(M=(E,I))，其中(E)是基础集，(I)是(E)的一些子集构成的集族(即(Isube 2^S))，称之为独立集，在独立集中的子集称之为独立的
拟阵可以用独立集(I)定义，则(I)需满足性质:
1.空集：有(emptyset in I)，所以有(I e emptyset)
2.遗传性：若(Asube B,Bin I)，则$ Ain I$
3.扩充性：若(exists A,Bin I,|A|>|B|)，则(exists iin A,(Bcup {i}) in I)
例子：对于(S={1,2,3})，({emptyset },{emptyset,{1}})是合法的独立集，但({emptyset,{1},{2},{3},{2,3}})不是，因为它不满足扩充性
({{1,2},{2,3},{1},{2},{3},{emptyset }})也是合法的独立集
对于(S={1,2,3,4,5}),(I={{1,2,3},{3,4,5},{1,2},{2,3},{1,3},{3,4},{3,5},{4,5},{1},{2},{3},{5},{emptyset}})不是合法的独立集，因为它不满足扩充性((A={1,2,3},B={3,4})时)
用基底和基定义拟阵(似乎是最简洁的描述)
基底:(E)的一个独立的极大子集称为其的一个基底，独立的极大子集即其加入任意元素得到的子集不独立
基:(E)的基(B)为其所有基底构成的集合
拟阵可以用基(B)定义，则(B)需满足性质:
1.非空：(B e emptyset)，最小的(B={emptyset})
2.交换公理：对于两个基底(a,b)，若用(b)中(a)没有的元素换掉一个(a)中原先的元素，得到的集合依然是基底
推论：基底等大，即(forall ain B,bin B,|a|=|b|)(否则就不满足扩充性)
例如：若({1,2},{1,3})是基底，则({2,3})也是基底(否则不满足扩充性)
可以得到拟阵的等价定义，且(I=igcup _{Tin B} 2^T)
用环路集定义拟阵
环路:(S)的一个子集是环路，则这个子集是一个极小的非独立集，即去掉任意一个元素都会称为独立集
所有环路构成的集合称为环路集(C)，如对于(E={1,2},I={emptyset,{1}})，环路集为({{2}})
拟阵可以用环路集(C)定义，则(C)需满足性质：
1.(C)可以为空(此时(I=P(S)))，且(emptyset ot in C)
2.环路互相之间不是真子集，即(exists ain C,bin C,asube bRightarrow a=b) (否则不满足遗传性)
3.若(exists ain C,bin C,a e b)以及一个元素(iin acap b)，则(acup b-{i})不是独立集
推论：(Asube I Leftrightarrow exists Bin C,Bsube A)
环路不一定等大
环路和基底的一些关系
1.环路和基底之间不能通过加减一个元素转化
2.基底加上一个元素得到的非独立集恰好包含一个环路
拟阵的秩
拟阵的秩：拟阵的任意一个基底的元素个数是其秩(r)
为了同下文的秩函数相对应，也可说(egin{aligned}r=max_{Rin I}{|R|}end{aligned})，即最大的独立集大小
用秩函数定义拟阵
对于元素集(S)
若可以定义一个在(2^S)上的秩函数(r(T))，满足以下性质:
1.大小有界:(r(T)in[0,|T|])
2.大小传递性:(Asube BRightarrow r(A)le r(B))
3.次模性:(r(Acup B)+r(Acap B)le r(A)+r(B))
那么可以用这样的一个秩函数定义一个拟阵(M=(S,r))，此时(r(T))为(2^T)中极大的独立集大小，且拟阵的独立集就是(I={T|Tsube S,r(T)=|T|})
例子
均匀拟阵：(U_n^k=(S,I),|S|=n,I={T|Tsube S,|T|leq k})
图拟阵：
对于无向图(G=(V,E))，它的生成拟阵是(M=(E,{T|Tsube E,T无环}))
它的最大独立子集大小为(G)的最大生成森林边数，每个最大生成森林都是基底
匹配拟阵：
对于无向图(G=(V,E))，它的匹配拟阵是(M=(V,{T|Tsube V,存在一个边匹配覆盖T}))
它的最大的独立子集大小为k最大匹配数，每个最优匹配的方案都是基底
异或线性基：
对于非负整数可重集合(S)，拟阵是(M=(S,{T|Tsube S,T中的元素任意异或不会得到0}))
(这是向量空间的线性基问题的一种)
注意分清楚 定义需要满足的条件 和 通过条件推导得到的性质 的区别 ，上面几种拟阵定义是等价的
一些应用
求最大权值独立子集
对于拟阵(M=(S,I))，给每个(S)中每个元素一个非负权值，定义一个集合的权值为所有元素权值和，要求最大权值的独立子集
这是一个非常简单的问题，直接从大到小能加入就加入即可，设最终选出的集合为(P)
证明:
1.(Pin B)，否则可以再加入元素
2.假设存在更优解(Qin B)，根据基底交换公理，一定可以用(P)中一个权值更大的元素换掉(Q)中一个元素，所以(Q)不是合法集合
在连通图拟阵上使用该算法，就是( ext{Kruskal})最小生成数算法
在异或线性基上使用该算法，可以求得最大权值线性基
拟阵交
对于同基础集的拟阵(M_1=(S,I_1),M_2=(S,I_2))，它们的交是独立集的交
但是它们的交不一定是拟阵
求解最大交:最小最大定理:
(egin{aligned} max_{Ain (I_1cup I_2)}{|T|}=min_{Rin S}{r_1(R)+r_2(S-R)}end{aligned})
这个东西的证明分为两步:
1.证明(maxleq min)
(|T|=|Tcap R|+|Tcap (S-R)|leq r_1(R)+r_2(S-R))
2.介绍找到两个最值的算法
这个算法的中心是，从空集开始扩展(T)，并且相应找到对应的(R)使得(|T|=r_1(R)+r_2(S-R))，此时答案已经充分了
求解拟阵交的算法基于一个构造的图
对于当前的答案(T)，构造一个有向二分图，两侧点集分别为(T,S-T)
对于分别在两侧的点(x,y)，
存在(x ightarrow y)的边: 当(T)中把(x)换成(y)之后是(M_1)的独立子集
存在(y ightarrow x)的边: 当(T)中把(y)换成(x)之后是(M_2)的独立子集
设对于(I_1,I_2)可行的增广元素集合为$X_1,X_2 $(即加入元素后依然独立的集合)
每次的增广过程可以描述为:
(1.如果(X_1cap X_2 e emptyset)，直接都加入(T))
2.构图，找到一条从(X_1)的点出发，到达(X_2)的的最短的路径(P)(广搜即可)，将(I)变为(Iigoplus P) (这里原文是对称差，但是异或大家都懂哈)
当不存在增广时，找到了最大的(T)，此时对应合法的(R)为({ein S|在图中存在e到达X_2的路径})
由于每次增广至少增加一个元素，该算法的复杂度上限为(O(r|S|^2))，其中(r)为拟阵的秩，(|S|^2)为边数
带权拟阵交
每个元素带权
在增广时，图上每个点加上点权(加入为正，删除为负)，每次求出点权最短路进行增广即可
拟阵交的应用
二分图匹配问题
二分图匹配匈牙利算法 是 求解拟阵交的问题 的一种特殊情况
对于二分图(G=(V_1,V_2,E))，构造
(M_1=(E,I={Tsube E|T中的边在V_1上没有公共点}))
(M_2=(E,I={Tsube E|T中的边在V_2上没有公共点}))
答案就是(M_1,M_2)交的最大值，匈牙利算法增广的过程是依次考虑(X_1)中的元素进行增广
(带权的二分图匹配问题，实际也是可以用拟阵解决的，但是好像( ext{KM})还是最棒的)
拟阵交还可以解决一些看起来很抽象的 带有两个限制的 (可能带权) 的问题，比如论文里下面的这个例子
(Colorful Tree): 对于一个无向图，每条边给定一个颜色和一个权值，求颜色不能重复的最大生成树
类似这样的问题可以转化为拟阵交问题，但是这个东西的局限性实在太大，也没有人敢动
update:
有生之年竟然用上了这个东西？
**模拟赛有人搞了一个题:
对于一个无向图(G=(V,E),E=(u,v,w))，其中(w)为每条边的颜色
要求选出一个最大的边集，满足：
1.每种颜色(i)选出的边不超过(c_i)条
2.选出的边不构成简单环
然后写了一次不太正规的拟阵交模板
令(M1)为个数的拟阵，(M2)为生成树拟阵
解释在代码里
int n,m,k;
int A[N],I[N];
// A为颜色个数的限制
int U[N],V[N],W[N],F[N];
// U,V,W为边
// F 为并查集
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }
int X[N],Y[N],P[N];
// 处理生成树的情况
vector <int> G[N];
int fa[N],fe[N],dep[N];
void dfs(int u,int f){
dep[u]=dep[fa[u]=f]+1;
for(int i:G[u]) {
int v=U[i]==u?V[i]:U[i];
if(v==f) continue;
fe[v]=i,dfs(v,u);
}
}
int main(){
freopen("forget.in","r",stdin),freopen("forget.out","w",stdout);
n=rd(),m=rd(),k=rd();
rep(i,1,k) A[i]=rd();
rep(i,1,m) U[i]=rd(),V[i]=rd(),W[i]=rd();
rep(i,1,n) F[i]=i;
while(1) {
int f=0;
// X, Y分别为 M1,M2的可拓展集合
// I 记录已经在选边方案里的边
rep(i,1,m) if(!I[i]) {
X[i]=A[W[i]]>0,Y[i]=Find(U[i])!=Find(V[i]);
// 如果X,Y有交，就直接加入集合
if(X[i] && Y[i]) {
A[W[i]]--,F[Find(U[i])]=Find(V[i]);
I[i]=1,f=i;
}
} else X[i]=Y[i]=0;
if(f) continue;
static queue <int> que;
while(!que.empty()) que.pop();
// 预处理当前的生成树，便于处理M2的限制
rep(i,1,n) G[i].clear();
rep(i,1,m) if(I[i]) G[U[i]].pb(i),G[V[i]].pb(i);
rep(i,1,n) dep[i]=0;
rep(i,1,n) if(!dep[i]) dfs(i,0);
// 从X中的某一个点出发
rep(i,1,m) if(X[i]) que.push(i),P[i]=-1;
else P[i]=0;
f=0;
// 广搜找交替 替换路径
while(!que.empty()) {
int u=que.front(); que.pop();
// 找到一条满足X->Y的交替路径
if(Y[u]){ f=u; break; }
if(I[u]) {
// u->v，交换之后满足M1
rep(v,1,m) if(!P[v] && !I[v] && A[W[v]]+(W[u]==W[v])) P[v]=u,que.push(v);
} else {
// 满足拟阵M2，即交换这条边之后还是生成树，可以从目前生成树上的环上选取能够替换的边
int x=U[u],y=V[u];
if(Find(x)!=Find(y)) {
rep(v,1,m) if(!P[v] && I[v])
P[v]=u,que.push(v);
} else {
while(x!=y) {
if(dep[x]<dep[y]) swap(x,y);
int i=fe[x];
if(!P[i]) P[i]=u,que.push(i);
x=fa[x];
}
}
}
}
if(!f) break;
// 放置交替方案
while(~f) {
A[W[f]]+=I[f]?1:-1;
I[f]^=1,f=P[f];
}
int cnt=0;
rep(i,1,m) if(I[i]) cnt++;
// 重构并查集
rep(i,1,n) F[i]=i;
rep(i,1,m) if(I[i]) F[Find(U[i])]=Find(V[i]);
}
int cnt=0;
rep(i,1,m) if(!I[i]) cnt++;
printf("%d
",cnt);
rep(i,1,m) if(!I[i]) printf("%d ",i);
}