【学习笔记】拟阵

学习笔记, 拟阵

超浅谈。证明挂不挂看心情（可以去看 18 年集训队论文《浅谈拟阵的一些拓展及其应用》）

拟阵

定义拟阵 $M = (S, \mathcal{I})$，表示一个定义在有限集 $S$ 上，独立集的集合是 $\mathcal{I}$ 的拟阵，显然 $\mathcal{I} \subseteq S$。

这里独立集是抽象概念。

拟阵的两条公理：

  • 遗传性：对于 $I \in \mathcal{I}$，$x \in I$，$I \setminus {x} \in \mathcal{I}$
  • 交换性：$I, J \in \mathcal{I}$，$|J| > |I|$，存在 $x \in J \setminus I$ 满足 $I \cup {x} \in \mathcal{I}$

任何组合优化问题（某种最优化问题）如果满足这两条公理，就具有拟阵结构，所有拟阵的定理在这个组合优化问题上成立。比如以下三种：

  1. 均匀拟阵：拟阵 $M_n^k = (S, \mathcal{I})$，其中 $|S| = n$，$\mathcal{I} = {I \subseteq S : |I| \leq k}$。显然满足遗传性和交换性。简单但有用的一个东西，可以把长相清真的限制拿来凑拟阵，做拟阵交。
  2. 图拟阵：仅对无向图成立。无向图 $G = (V, E)$，图拟阵 $M = (E, \mathcal{I})$，$\mathcal{I} = {F \subseteq E: F 无环}$，即，独立集是生成森林。
  3. 匹配拟阵：$G = (V, E)$，匹配拟阵 $M = (V, \mathcal{I})$，$\forall \mathcal{I}, 存在匹配覆盖 \mathcal{I} 中所有点$。二分图匹配问题是个拟阵。

秩函数

对于拟阵 $M = (S, \mathcal{I})$，定义 $r(U)$ 为集合 $U \subseteq S$ 的秩函数，表示 $U$ 中极大独立集的大小。

秩函数满足拟阵的两条公理。因此满足秩函数的性质的组合优化问题具有拟阵结构。

基 & 环

  • 基：极大独立集。加任何一个元素都会变成非独立集。同个拟阵的所有基，大小相同。
    • 基交换定理：对于两个基 $A$、$B$，$A \neq B$，对于任意一个 $x \in A \setminus B$，都存在 $y \in B \setminus A$，满足 $A - {x} + {y} \in \mathcal{I}$
    • 强基交换定理：对于两个基 $A$、$B$，$A \neq B$，对于任意一个 $x \in A \setminus B$，都存在 $y \in B \setminus A$，满足 $A - {x} + {y}$ 和 $B - {y} + {x}$ 都是拟阵的基。
  • 环：极小非独立集。减任何一个元素都会变成独立集。

拟阵在贪心的应用

将元素按照权值 $\omega$ 降序排列，维护答案集合 $I$，初始 $I = \emptyset$，顺次考虑每个元素 $x_i$，若 $I \cup {x_i} \in \mathcal{I}$ 则加入 $x_i$。

正确性证明：

  • $I$ 是拟阵的一个基：归纳证明，记 $I_i$ 表示在 $i$ 处的 $I$ 版本。若 $I_i$ 是个基，则讨论 $I_{i + 1}$：
    • 若 $r(I_{i + 1}) = r(I_i)$，仍是基。
    • 若 $r(I_{i + 1}) > r(I_i)$，若 $I_i \cup {x_{i + 1}}$ 是独立集则仍是基，否则新并进去的元素 $\in I_i$，说明 $I_i$ 不是基，矛盾。
  • 最优性：考虑反证，若与最优解不同的选择第一次出现在 $x_i$，最优解选择了 $x_i’$，那么 $\omega(x_i) > \omega(x_i’)$，$x_i < i’$，那么必然存在另一对不同选择 $x_j’$ 和 $x_j$ 满足 $x_j’ < x_j$。根据基交换定理，$I - {x_j’} + {x_j} \in \mathcal{I}$，贪心算法一定会先选择 $x_j’$ 的。

嘿嘿，还是现实的问题有意思㗅着爽。MST、二分图最大匹配都是拟阵上的最优化问题，可以用拟阵说明他们的正确性。（就好比可以用费用流说明凸性）

对偶拟阵

算是补充定义？做题会用到，但和拟阵交没什么关系。

定义：拟阵 $M = (S, \mathcal{I})$ 的对偶拟阵 $M^* = (S, \mathcal{I^*})$，$\mathcal{I^*} = {I: 存在 M 中的基 B \subseteq S \setminus I}$，即从 $S$ 中删掉 $I$ 后还存在基。

对偶拟阵的秩函数 $r’(U)$ 的意义也很显然了，公式化讲得更清楚：$r’(U) = \max\limits_{I \subseteq U, I \in \mathcal{I^*}} |I|$

推下去，$r^*(U) = |U| - r(S) + r(S \setminus U)$。

一个拟阵对偶两次又回来了。这可以从秩函数看出：$r(S \setminus U) \rightarrow r^*(U) \rightarrow r(S \setminus U)$

可以从秩函数角度证明拟阵对偶后还是个拟阵。

经典应用嘛，还是图拟阵。「图连通」问题本身不是拟阵结构，但它可以用图拟阵的对偶拟阵做。注意是用对偶拟阵做！！！而不是把对偶拟阵再对偶，那样啥都不是了。

拟阵交

求同时属于两个拟阵的独立集中最大的独立集。两个拟阵的交不是拟阵，否则直接贪心就行…… 那么怎么做呢？

最小最大定理

$\max\limits_{I \in \mathcal{I_1} \cap \mathcal{I_2}} |I| = \min\limits_{U \subseteq S}( r_1(U) + r_2(S\setminus U) )$

我们只要求出一组 $I$ 和 $U$ 满足这个定理，就解决了拟阵交问题。

交换图

定义：给定两个拟阵 $M_1$, $M_2$，和一个集合 $I \in \mathcal{I_1} \cap \mathcal{I_2}$，定义关于 $I$ 的交换图 $D_{M_1, M_2}(I)$ 是如下的二分图：两部分点集由 $I$ 和 $S \setminus I$ 组成。

  • 一条从 $y \in I$ 指向 $x \in S \setminus I$ 的边存在，当且仅当 $I - {y} + {x} \in \mathcal{I_1}$。
  • 一条从 $x \in S \setminus I$ 指向 $y \in I$ 的边存在，当且仅当 $I - {y} + {x} \in \mathcal{I_2}$。

算法流程

  1. 令 $X_1 = {x \in S \setminus I | I \cup {x} \in \mathcal{I_1} }$, $X_2 = {x \in S \setminus I | I \cup {x} \in \mathcal{I_2} }$。
  2. 增广，每次找一条 $X_1$ 到 $X_2$ 的最短路 $P$，令 $I$ 变为 $I \Delta P$（$\Delta$ 为对称差）。每次增广会扩张恰好 $1$ 个元素（显然，类比二分图增广过程）。
  3. 重复增广直到找不到 $X_1$ 到 $X_2$ 的路径。

算法运行结束后，$|I| = r_1(U) + r_2(S \setminus U)$。

关于时间复杂度，令 $r = \max(r_1(S), r_2(S))$，$n = |S|$，图有 $n$ 个点、$rn$ 条边，找最短路单次 $O(n + m)$，增广次数不超过 $r$（每次增广 $|I|$ 至少增加 $1$），总复杂度 $O(r^2n)$。

实现时，设源汇点 $s$、$t$，若 $x \notin I$ 满足 $I + {x} \in I_1$，就连边 $s \rightarrow x$，若 $I + {x} \in I_2$ 就连边 $x \rightarrow t$。

带权拟阵交

带权了。令点权为 $w(x)$。

扩展最小最大定理

$\max\limits_{I \in \mathcal{I_1} \cap \mathcal{I_2}} \sum\limits_{e \in I} \omega(e) = \min\limits_{\omega_1, \omega_2: \forall x, \omega_1(x) + \omega_2(x) = \omega(x)} ( \max\limits_{I \in \mathcal{I_1}} \omega_1(I) ) + ( \max\limits_{I \in \mathcal{I_2}} \omega_2(I) )$

  • $x \in I$, $w(x) = -\omega(x)$
  • $x \in S \setminus I$, $w(x) = \omega(x)$

以最大权为例，求最长路，第一关键字是点权最大（论文这里出错了），第二关键字是路径最短。交换图上不存在正权环，因此可解。

多个拟阵交是 NP-hard 的。

拟阵的并？咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕

习题

$NAIPC18G-Rainbow Graph$

众所周知，图连通不是拟阵结构。但是删边判连通可以用图拟阵的对偶拟阵做（连通图必然存在树！）。

有两个限制，要求拟阵交。

倒着做，每增广一次表示对偶拟阵大小 +1。做最小带权拟阵交。

代码不放了，跟 奶糖 那道差不多。

$Milk Candy$

恰好怎么搞？先限制不超过 $c - k$ 条，然后不停增广增广。由于求最大权拟阵，一定会取到 $c - k$ 条。

两个限制：

  • 每个位置都要至少被覆盖一次。这是图拟阵的对偶。
  • 以及每种颜色删的边不超过 $c - k$ 条。这是均匀拟阵。

做最大拟阵交即可！

最后还是要判一下是否 $< c - k$。

sb 错误调一年？

code 
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define per(i, x, y) for (int i = x; i >= y; i--)
#define vi vector<int>
#define Go(i, x, v) for (int i = 0, x = (i == v.size() ? 0 : v[i]); i < v.size(); i++, x = (i == v.size() ? 0 : v[i]))
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define gc getchar
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <class T> void rd(T &x) {
  x = 0; char ch = gc(); int f = 1;
  for (; !isdigit(ch); ch = gc()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + ch - '0';
  x *= f;
}
template <class T> void cmin(T &x, T y) { x = min(x, y); }
template <class T> void cmax(T &x, T y) { x = max(x, y); }
const int mod = 1e9 + 7;
void Add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void Sub(int &x, int y) { x += mod - y; if (x >= mod) x -= mod; }
void Mul(int &x, int y) { x = (ll)x * y % mod; }
int add(int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
int sub(int x, int y) { x += mod - y; if (x >= mod) x -= mod; return x; }
int mul(int x, int y) { return (ll)x * y % mod; }
int qpow(int a, int b) { int ret = 1; for (; b; b >>= 1, Mul(a, a)) if (b & 1) Mul(ret, a); return ret; }
/* ============ Header Template ============ */
const int N = 90;
int n, m, cost[N], bel[N];
int lnk[N], cnt, nxt[N << 1], to[N << 1];
vi in;
struct node {
  int lim[N], c[N], k[N];
  bool chk(vi in) {
    rep(i, 1, m) lim[i] = c[i] - k[i];
    rep(i, 1, cnt / 2) if (in[i]) --lim[bel[i]];
    rep(i, 1, m) if (lim[i] < 0) return 0;
    return 1;
  }
};
bool chk(node a) {
  rep(i, 1, m) if (a.lim[i]) return 0;
  return 1;
}
struct graph {
  bool vis[N];
  graph(int N = 0) {
    rep(i, 0, N + 2) lnk[i] = 0; cnt = 1;
  }
  void adde(int x, int y) {
    to[++cnt] = y, nxt[cnt] = lnk[x], lnk[x] = cnt;
  }
  void dfs(int x) {
    if (vis[x]) return;
    vis[x] = 1;
    for (int i = lnk[x]; i; i = nxt[i])
      if (!in[i / 2]) dfs(to[i]);
  }
  bool chk(vi in) {
    rep(i, 1, n) vis[i] = 0;
    dfs(1);
    rep(i, 1, n) if (!vis[i]) return 0;
    return 1;
  }
};
namespace Matroid {
  #define inf 0x3f3f3f3f
  int dis[N], pre[N], S, T;
  bool inq[N];
  queue<int> q;
  vi e[N];
  void add(int x, int y) {
    e[x].pb(y);
  }
  template <class dt, class M1, class M2>
  bool find(int n, dt w[], M1 m1, M2 m2, vi &in) {
    S = n + 1, T = n + 2;
    rep(i, 1, T) e[i].clear();
    rep(i, 1, n) if (in[i])
      rep(j, 1, n) if (!in[j]) {
        in[i] ^= 1, in[j] ^= 1;
        if (m1.chk(in)) add(i, j);
        if (m2.chk(in)) add(j, i);
        in[i] ^= 1, in[j] ^= 1;
      }
    rep(i, 1, n) if (!in[i]) {
      in[i] ^= 1;
      if (m1.chk(in)) add(S, i);
      if (m2.chk(in)) add(i, T);
      in[i] ^= 1;
    }
    rep(i, 1, T) dis[i] = -inf, inq[i] = 0, pre[i] = -1;
    q.push(S), inq[S] = 1, dis[S] = 0;
    while (q.size()) {
      int x = q.front(); q.pop(); inq[x] = 0;
      Go(i, y, e[x]) {
        int v = in[y] ? -w[y] : w[y];
        if (dis[y] < dis[x] + v) {
          dis[y] = dis[x] + v;
          pre[y] = x;
          if (!inq[y]) inq[y] = 1, q.push(y);
        }
      }
    }
    if (dis[T] == -inf) return 0;
    while (pre[T] != S) in[T = pre[T]] ^= 1;
    return 1;
  }
  template <class dt, class M1, class M2>
  vector<dt> intersaction(int n, dt w[], M1 m1, M2 m2) {
    while (find(n, w, m1, m2, in));
    return in;
  }
}; using namespace Matroid;
int main() {
  int cas; rd(cas);
  while (cas--) {
    rd(n), rd(m);
    ++n;
    graph g(n + 5);
    node tmp;
    rep(i, 1, m) {
      rd(tmp.c[i]), rd(tmp.k[i]);
      rep(j, 1, tmp.c[i]) {
        int l, r, w; rd(l), rd(r), rd(w); ++l, ++r;
        g.adde(l - 1, r), g.adde(r, l - 1);
        bel[cnt / 2] = i;
        cost[cnt / 2] = w;
      }
    }
    in.clear();
    in.resize(cnt / 2 + 5);
    vi res = Matroid::intersaction(cnt / 2, cost, g, tmp);
    int ans = 0;
    rep(i, 1, cnt / 2) if (!in[i]) ans += cost[i];
    if (g.chk(res) && tmp.chk(res) && chk(tmp)) printf("%d\n", ans);
    else puts("-1");
  }
  return 0;
}

元旦老人与丛林

快乐的咕了。学不动了放过我吧 /dk 我要找我的 JOI 接受心灵慰藉去