【模板】拟阵交

【模板】拟阵交

给定边集 \(E\)，每条边都有一个颜色。给定数组 \(\{C_i\}\)。选出最大的子集使得：子集中找不到一个简单环；子集中颜色 \(c\) 的边的出现次数不超过 \(C[c]\)。

本题即为拟阵交的模板题，需要求解图拟阵和划分拟阵的交中最大的独立集。可以证明，它们的交还是拟阵，故使用拟阵交算法解决该问题。

请参考：从拟阵基础到 Shannon 开关游戏 - 洛谷专栏

拟阵的定义

来源是上面贴的参考资料。

拟阵是一个对向量空间中线性独立概念的概括与归纳的数学结构。

通俗的说，拟阵是描述独立关系的结构。

一个拟阵 \(\mathcal M = \langle X,\mathcal I\rangle\)，其中 \(X\) 被称为 Ground Set，\(\mathcal I\) 被称为 Family of Sets，即 \(X\) 的独立子集的集合。如果一个集合 \(I \in \mathcal I\) （请注意 \(I\) 和 \(\mathcal I\) 之间的区别，一个是 I，一个是 \mathcal I，他们是不同的），则他是 \(X\) 的一个独立子集。

【性质】一个拟阵必须有下列性质：

  1. \(X\) 是一个有穷集合。
  2. （遗传性）一个独立子集的所有子集都是独立子集，即对于所有的 \(I \in \mathcal I, I' \subseteq I\)，则有 \(I' \in \mathcal I\)。空集必须是独立集。
  3. （交换性质）若 \(A,B \in \mathcal I, |A| < |B|\)，则 \(\exists x \in B \setminus A\) 使得 \(A + \{x\} \in \mathcal I\)。

如果我们需要证明一个形如 \(\langle X, \mathcal I\rangle\) 的东西是拟阵，我们只需要证明他满足以上 3 条性质即可。

这是一个拟阵：\(\mathcal M = \langle \{x, y, z\},\mathcal \{\varnothing, \{x\}, \{y\},\{z\},\{x, y\}, \{x, z\}\}\rangle\)。

拟阵的秩就是 \(X\) 的最大独立子集的大小。

求拟阵的秩

其实是 Kruskal 算法的一种体现。也就是先把 \(X\) 中的元素按照权值排序（如果元素带权），然后维护一个 \(I\) 初始为空，枚举 \(X\) 中元素，如果它加入 \(I\) 后仍然在 \(\mathcal I\) 中，则加入；否则以后也不会再加入它了，可以扔掉。最后得到的 \(I\) 的大小就是拟阵的秩。

拟阵交

拟阵和拟阵的交不一定是拟阵。当它真的不是拟阵的时候，我们使用拟阵交算法求出它的秩；否则使用刚才说的算法直接求拟阵的秩就好了。

以下是无权拟阵交算法的具体步骤。由于带权拟阵交还不知道为什么对，暂时按下不表。

  1. 拟阵 A（图拟阵）：没有简单环的集合是独立集。
  2. 拟阵 B（划分拟阵）：颜色 \(c\) 的边的出现次数都不超过 \(C[c]\) 的集合是独立集。
  3. 据此写出两个拟阵的代码，支持设定一个 \(I\)（build），和给定 \(x\) 返回 \(I\cup\{x\}\) 是否在拟阵中（oracle）。
  4. 从 \(I=\varnothing\) 开始，重复以下步骤：
    1. 建一张空的有向二分图，\(I\) 是左部点，\(E\setminus I\) 是右部点。
    2. 枚举 \(i\in I\)，将两个拟阵的 \(I'\) 设置为当前的 \(I\setminus\{i\}\)。枚举 \(j\not\in I\)，若拟阵 A oracle(j) 则连边 \(i\to j\)；若拟阵 B oracle(j) 则连边 \(j\to i\)；
    3. 准备进行 BFS 找增广路。设置拟阵 A 的 \(I'=I\)，将所有 \(i\not\in I\) 且能 oracle 的 \(i\) 入队。
    4. 进行 BFS，注意要维护最短的增广路，最短就是点数最少的意思；还要维护路径的前驱。
    5. 设置拟阵 B 的 \(I'=I\)，枚举所有 \(i\not\in I\) 且能 oracle 的 \(i\)，找出最短路最短的那个 \(i\)。
    6. 从那个最短的点往回跳，将增广路上所有点在 \(I\) 的状态取反。
  5. 算法无法找出增广路时，算法结束，\(I\) 就是答案。

代码

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#define endl "\n"
#endif
using LL = long long;
template <int N>
struct unionset {
  int fa[N], siz[N];
  unionset() { iota(fa, fa + N, 0), fill_n(siz, N, 1); }
  int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
  bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (siz[x] < siz[y]) swap(x, y);
    fa[y] = x, siz[x] += siz[y];
    return true;
  }
};
constexpr int N = 510;
struct edge {
  int u, v, w;
};
int n, m, c[N], K;
bool vis[N];
edge e[N];
struct matroid_graph {
  unionset<N> dsu;
  void build(int ban) {
    dsu = unionset<N>();
    for (int i = 1; i <= m; i++) if (vis[i] && i != ban) {
      dsu.merge(e[i].u, e[i].v);
    }
  }
  bool oracle(int x) {
    return dsu.find(e[x].u) != dsu.find(e[x].v);
  }
};
struct matroid_color {
  int cnt[N];
  void build(int ban) {
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= m; i++) if (vis[i] && i != ban) {
      cnt[e[i].w] += 1;
    }
  }
  bool oracle(int x) {
    return cnt[e[x].w] < c[e[x].w];
  }
};
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#ifndef NF
#endif
#endif
  cin >> n >> m >> K;
  for (int i = 1; i <= K; i++) cin >> c[i];
  for (int i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w;
    e[i] = {u, v, w};
  }
  matroid_graph m1;
  matroid_color m2;
  memset(vis, false, sizeof vis);
  static bool g[N][N];
  while (true) {
    memset(g, false, sizeof g);
    for (int i = 1; i <= m; i++) if (vis[i]) {
      m1.build(i), m2.build(i);
      for (int j = 1; j <= m; j++) if (!vis[j]) {
        if (m1.oracle(j)) g[i][j] = true;
        if (m2.oracle(j)) g[j][i] = true;
      }
    }
    static int pre[N], dis[N];
    memset(dis, 0x3f, sizeof dis);
    queue<int> q;
    m1.build(0);
    for (int i = 1; i <= m; i++) if (!vis[i] && m1.oracle(i)) q.push(i), pre[i] = 0, dis[i] = 0;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v = 1; v <= m; v++) if (g[u][v] && dis[v] > dis[u] + 1) dis[v] = dis[u] + 1, pre[v] = u, q.push(v);
    }
    m2.build(0);
    int rp = -1;
    for (int i = 1; i <= m; i++) if (!vis[i] && m2.oracle(i) && (rp == -1 || dis[rp] > dis[i])) rp = i;
    if (rp == -1 || dis[rp] > 1e9) break;
    while (rp) vis[rp] ^= 1, rp = pre[rp];
  }
  int cnt = 0;
  for (int i = 1; i <= m; i++) cnt += !vis[i];
  cout << cnt << endl;
  for (int i = 1; i <= m; i++) if (!vis[i]) cout << i << " ";
  cout << endl;
  return 0;
}

所以谁能告诉我，为什么拟阵（matroid）会有一个甲骨文（oracle）操作呢？

posted @ 2026-01-21 21:54  caijianhong  阅读(23)  评论(0)    收藏  举报