拟阵

大量基础定义警告，参考了 wiki 和2018论文《浅谈拟阵的一些拓展及其应用》，如果想看大段详细证明请移步论文。

拟阵的概念比较抽象，有多种定义方法，结合这些定义方法可以更具体地了解拟阵的基础性质。

前言

很多问题可以转化为拟阵，但是并不是所有问题都可以通过简单的拟阵操作得到答案。

在具体问题中，很多时候有着更优的算法解决拟阵运算无法解决的操作。

但是对于一个奇怪的问题，如果转化为类似拟阵的操作后，就有很多性质可以拿过来套。在 OI 中，应用于拟阵的常见算法与二分图上的一些算法相当相似。

拟阵的应用，更多还是用 诸多的性质 把复杂,抽象问题向更简单的方向转化(便于乱搞)。

也可以便于简化问题的证明，所以这个东西了解一下也差不多了。

(不会有人丧心病狂到专门出一个拟阵交的题吧)。

符号及约定

\(|S|\) 集合大小。

\(S-T\)，删除 \(S\) 中在 \(T\) 中的元素。

\(a\Rightarrow b\) 若 \(a\) 则 \(b\)。

\(a\Leftrightarrow b\)，\(a,b\) 等价。

\(a\in b\) 元素 \(a\) 是集合 \(b\) 中的一个元素。

\(a\sube 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\) 的一些子集构成的集族(即 \(I\sube 2^S\) )，称之为独立集，在独立集中的子集称之为独立的。

拟阵可以用独立集 \(I\) 定义，则 \(I\) 需满足性质:

1. 空集：有 \(\emptyset \in I\)，所以有 \(I\ne \emptyset\)。
2. 遗传性：若 \(A\sube B,B\in I\)，则 $ AI$。
3. 扩充性：若 \(\exists A,B\in I,|A|>|B|\)，则 \(\exists i\in A,(B\cup \{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\ne \emptyset\)，最小的 \(B=\{\emptyset\}\)。
2. 交换公理：对于两个基底 \(a,b\)，若用 \(b\) 中 \(a\) 没有的元素换掉一个 \(a\) 中原先的元素，得到的集合依然是基底。

推论：基底等大，即 \(\forall a\in B,b\in B,|a|=|b|\) （否则就不满足扩充性）。

例如：若 \(\{1,2\},\{1,3\}\) 是基底，则 \(\{2,3\}\) 也是基底（否则不满足扩充性）。

可以得到拟阵的等价定义，且 \(I=\bigcup _{T\in B} 2^T\)。

用环路集定义拟阵

环路: \(S\) 的一个子集是环路，则这个子集是一个极小的非独立集，即去掉任意一个元素都会称为独立集。

所有环路构成的集合称为环路集 \(C\)，如对于 \(E=\{1,2\},I=\{\emptyset,\{1\}\}\)，环路集为 \(\{\{2\}\}\)。

拟阵可以用环路集 \(C\) 定义，则 \(C\) 需满足性质：

1. \(C\)可以为空(此时\(I=P(S)\))，且\(\emptyset \not \in C\)。
2. 环路互相之间不是真子集，即\(\exists a\in C,b\in C,a\sube b\Rightarrow a=b\) (否则不满足遗传性)。
3. 若\(\exists a\in C,b\in C,a\ne b\)以及一个元素\(i\in a\cap b\)，则\(a\cup b-\{i\}\)不是独立集。

推论：\(A\sube I \Leftrightarrow \nexists B\in C,B\sube A\)。

环路不一定等大。

环路和基底的一些关系

1. 环路和基底之间不能通过加减一个元素转化。

2. 基底加上一个元素得到的非独立集恰好包含一个环路。

拟阵的秩

拟阵的秩：拟阵的任意一个基底的元素个数是其秩 \(r\)。

为了同下文的秩函数相对应，也可说 \(\begin{aligned}r=\max_{R\in I}\{|R|\}\end{aligned}\)，即最大的独立集大小。

用秩函数定义拟阵

对于元素集 \(S\)，

若可以定义一个在 \(2^S\) 上的秩函数 \(r(T)\)，满足以下性质：

1. 大小有界： \(r(T)\in[0,|T|]\)。

2. 大小传递性：\(A\sube B\Rightarrow r(A)\le r(B)\)。

3. 次模性： \(r(A\cup B)+r(A\cap B)\le r(A)+r(B)\)。

那么可以用这样的一个秩函数定义一个拟阵 \(M=(S,r)\)，此时 \(r(T)\) 为 \(2^T\) 中极大的独立集大小，且拟阵的独立集就是 \(I=\{T|T\sube S,r(T)=|T|\}\)。

例子

均匀拟阵：\(U_n^k=(S,I),|S|=n,I=\{T|T\sube S,|T|\leq k\}\)。

图拟阵：

对于无向图 \(G=(V,E)\)，它的生成拟阵是 \(M=(E,\{T|T\sube E,T无环\})\)。

它的最大独立子集大小为 \(G\) 的最大生成森林边数，每个最大生成森林都是基底。

匹配拟阵：

对于无向图 \(G=(V,E)\)，它的匹配拟阵是 \(M=(V,\{T|T\sube V,存在一个边匹配覆盖T\})\)。

它的最大的独立子集大小为 \(k\) 最大匹配数，每个最优匹配的方案都是基底。

异或线性基：

对于非负整数可重集合 \(S\)，拟阵是 \(M=(S,\{T|T\sube S,T中的元素任意异或不会得到0\})\)。

(这是向量空间的线性基问题的一种)

---

注意分清楚 定义需要满足的条件 和 通过条件推导得到的性质 的区别 ，上面几种拟阵定义是等价的

一些应用

求最大权值独立子集

对于拟阵 \(M=(S,I)\)，给每个 \(S\) 中每个元素一个非负权值，定义一个集合的权值为所有元素权值和，要求最大权值的独立子集。

这是一个非常简单的问题，直接从大到小能加入就加入即可，设最终选出的集合为 \(P\)。

证明:

1. \(P\in B\)，否则可以再加入元素

2. 假设存在更优解 \(Q\in B\)，根据基底交换公理，一定可以用 \(P\) 中一个权值更大的元素换掉 \(Q\) 中一个元素，所以 \(Q\) 不是合法集合。

在连通图拟阵上使用该算法，就是 \(\text{Kruskal}\) 最小生成数算法。

在异或线性基上使用该算法，可以求得最大权值线性基。

拟阵交

对于同基础集的拟阵 \(M_1=(S,I_1),M_2=(S,I_2)\)，它们的交是独立集的交。

但是它们的交不一定是拟阵。

求解最大交:最小最大定理：

\(\begin{aligned} \max_{A\in (I_1\cup I_2)}\{|T|\}=\min_{R\in S}\{r_1(R)+r_2(S-R)\}\end{aligned}\)

这个东西的证明分为两步:

1. 证明\(\max\leq \min\)。

\(|T|=|T\cap R|+|T\cap (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\rightarrow y\) 的边: 当 \(T\) 中把 \(x\) 换成 \(y\) 之后是 \(M_1\) 的独立子集。

存在 \(y\rightarrow x\) 的边: 当 \(T\) 中把 \(y\) 换成 \(x\) 之后是 \(M_2\) 的独立子集。

设对于 \(I_1,I_2\) 可行的增广元素集合为 $X_1,X_2 $ （即加入元素后依然独立的集合）。

每次的增广过程可以描述为：

1. 如果 \(X_1\cap X_2\ne \emptyset\)，直接都加入 \(T\) 。
2. 构图，找到一条从 \(X_1\) 的点出发，到达 \(X_2\) 的最短的路径 \(P\) (广搜即可)，将 \(I\) 变为 \(I\bigoplus P\) （这里原文是对称差，但是异或大家都懂哈）。

当不存在增广时，找到了最大的 \(T\)，此时对应合法的 \(R\) 为 \(\{e\in S|在图中存在e到达X_2的路径\}\)。

由于每次增广至少增加一个元素，该算法的复杂度上限为 \(O(r|S|^2)\)，其中\(r\) 为拟阵的秩，\(|S|^2\) 为边数。

带权拟阵交

每个元素带权：

在增广时，图上每个点加上点权（加入为正，删除为负），每次求出点权最短路进行增广即可。

拟阵交的应用

二分图匹配问题

二分图匹配匈牙利算法 是 求解拟阵交的问题 的一种特殊情况。

对于二分图 \(G=(V_1,V_2,E)\)，构造：

\(M_1=(E,I=\{T\sube E|T中的边在V_1上没有公共点\})\)，

\(M_2=(E,I=\{T\sube E|T中的边在V_2上没有公共点\})\)。

答案就是 \(M_1,M_2\) 交的最大值，匈牙利算法增广的过程是依次考虑 \(X_1\) 中的元素进行增广。

（带权的二分图匹配问题，实际也是可以用拟阵解决的，但是好像 \(\text{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(){
	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\n",cnt);
	rep(i,1,m) if(!I[i]) printf("%d ",i);
}