拟阵

$M(S,I)$表示一个拟阵，其中I是S的某些子集的集合，满足这些子集在某种定义下是独立的一个拟阵M需要满足如下三个性质：

• 空集属于I
• 若集合A属于I，则A的任意一个子集也属于I（遗传性）
• 若集合A属于I，任意一个size大于A的属于I的集合B中总能找到元素加入A，使其仍在I中（交换性）

满足以上定义的最好的解释例子就是线性无关向量组。基：最大独立集，即I中size最大的那个子集环：最小的非独立集，去掉任意元素后就是一个独立集

典型的拟阵：

• uniform matroid：size$\leq k$的子集
• linear matroid：线性无关的子集
• colorful matroid：每个元素有一种颜色，如果一个集合中所有元素颜色各不相同就独立
• graphic matroid：每个元素是一条边，一个集合中的边没有环就独立
• 上一个拟阵的对偶拟阵：对于一个集合，保留在S中且不在该集合中的所有边后，整个图连通则独立。注：必须是删边，如果是考虑集合中的边连通的话，显然不满足遗传性。

拟阵交考虑现在有两个拟阵（其中的一个独立集本质上就代表着满足了某种约束的集合），那么我们要求同时满足这两个拟阵的约束条件下的最大独立集，这时候就要用到拟阵交了。该算法的流程是不断维护当前的共同独立集I，然后尝试加入一个新的元素s：定义一种交换图，对于任意两个元素x，y，若满足$x\in I, y \notinI,I-\{x\}+\{y\}\in{I_1}$​，就从x向y连一条有向边；若满足$x\in I, y\notin I,I-\{x\}+\{y\}\in{I_2}$​，就从y向x连一条有向边。简单说来就是如果把I中的某个元素x替换成没有选的某个元素y后，如果该独立集符合$I_1$​的定义，就加一条$x\rightarrowy$的边，如果符合$I_2$​的定义，就加一条$x \leftarrow y$的边。对于所有不在I中的元素x，若$I+\{x\}\in I_1$​，则源点S向其连边对于所有不在I中的元素x，若$I+\{x\}\in I_2$​，则其向汇点T连边然后从S向T跑一遍最短路，如果有这样的路径就把路径上的所有元素的状态取反（对称差）上述过程称为一次增广不断进行增广操作就可以得到最大独立集了复杂度为$O(r^2n(C_1+C_2))$，其中r为秩，$C_1$​和$C_2$​分别表示M1和M2检查当前集合是否为独立集的调用次数再考虑如果每个元素是带权的话，其实也很简单，如果一个元素当前在I，就把它的权值定为$-w$，否则定为$w$，然后跑最长路就可以得到最大权独立集了。上述算法的一个瓶颈其实是在检查是否为独立集上，这点一定要仔细实现。要支持加入一个元素判断是否还是独立集，删除一个元素并加入一个元素判断是否是独立集

bool aug()
{
  int S = n, T = n + 1;
  for(int i=0; i<n; i++) if(in[i])
    for(int j=0; j<n; j++) if(!in[j])
    {
      in[i] = 0, in[j] = 1;
      if(m1.check(in)) G[i].push_back(j);
      if(m2.check(in)) G[j].push_back(i);
      in[i] = 1, in[j] = 0;
    }
  for(int i=0; i<n; i++) if(!in[i])
  {
    in[i] = 1;
    if(m1.check(in)) G[S].push_back(i);
    if(m2.check(in)) G[i].push_back(T);
    in[i] = 0;
  }
  vector<int> dis(n+2, -inf), pre(n+2), inq(n+2);
  queue<int> q;
  q.push(S), dis[S] = 0;
  while(!q.empty())
  {
    int u = q.front(); q.pop();
    inq[u] = 0;
    int cost = 0;
    if(u<n) cost = in[u] ? -w[u] : w[u];
    for(int v : G[u])
    {
      if(dis[v]<dis[u]+cost)
      {
        dis[v] = dis[u] + cost;
        pre[v] = u;
        if(!inq[v]) q.push(v), inq[v] = 1;
      }
    }
  }
  if(pre[T]==-1) return false;
  for(int x=pre[T]; x!=S; x=pre[x]) in[x] ^= 1;
  return true;
}