Dyd's Blog

He who has a strong enough why can bear almost any how.

Dilworth定理

Posted on In
Symbols count in article: 5.6k Reading time ≈ 5 mins.

一般用于图论的转化……吧？

Dilworth定理

在开始前，必须先有些基础的数学知识

定义

  • $<x, y> \in R \Leftrightarrow xRy \Leftrightarrow x \preceq y$ ，其中 $x, y$ 是两个元素， $R, \preceq$ 是某种二元关系；上式的含义是有序对 $x, y$ 满足关系 $R(\preceq)$

  • 自反性：对于某种关系 $\preceq$ 和在它定义中的元素 $x$ ，若保证 $x \preceq x$ 则称 $\preceq$ 有自反性

  • 反对称性：对于某种关系 $\preceq$ 和若在它定义中任意两个不同元素 $x, y$ ，$x \preceq y, y \preceq x$ 不能同时成立

  • 传递性：对于某种关系 $\preceq$ 和在它定义中的元素 $x, y, z$ ，若 $x \preceq y, y \preceq z$ ，则必有 $x \preceq z$

  • 偏序关系：通俗来讲就是两个元素的大小关系，如果要形式化的话：

    对于集合 $A \ne \varnothing$ ，存在二元关系 $R \subseteq A \times A$ ，满足自反性、反对称、传递性，我们就称 $R$ 是 $A$ 上的偏序关系；显然，数上的小于等于，大于等于（ $\le, \ge$ ），集合上的包含（ $\subseteq$ ），正整数上的整除（ $\mid$ ）都是偏序关系

  • 严格偏序、非严格偏序：以上定义的全部都是非严格偏序（严格偏序不满足自反性），在已经定义了非严格偏序的基础上，我们可以自然地推导出严格偏序的定义：对于 $x, y \in A$ ， $x \prec y$ 当且仅当 $x \preceq y$ 且 $x \ne y$

  • 全序：对于集合 $A$ 和定义在其上的偏序关系 $\preceq$ ，若 $\forall x, y \in A$ 都有 $x \preceq y$ 或者 $y \preceq x$ （也就是任意两元素都可比），则称这个偏序关系为全序

  • 偏序集：对于集合 $A$ 和定义在其上的偏序关系 $\preceq$ 组成的有序对 $<A, \preceq>$ 称为偏序集

  • 链：称 $A’ \subseteq A$ 为偏序集 $<A, \preceq>$ 的一条链当且仅当 $\preceq$ 是 $A’$ 上的全序

  • 反链：称 $A’ \subseteq A$ 为偏序集 $<A, \preceq>$ 的一条反链当且仅当 $\forall x, y \in A’$ 且 $x \ne y$ ， $x \preceq y, y \preceq x$ 都不成立

  • 最小链覆盖（划分）、最小反链覆盖（划分）：对于偏序集 $<A, \preceq>$ ，把 $A$ 划分为若干条链的方案称为链覆盖，其中链数最少的称为最小链覆盖；最小反链覆盖类似定义

  • 极大元、极小元：对于偏序集 $<A, \preceq>$ ，若 $x \in A$ 且对于 $A$ 中任意一个异于 $x$ 的元素 $y$ ，都不存在 $x \preceq y$ （要么 $x$ 比 $y$ “大”，要么不可比），则称 $x$ 为偏序集的一个极大元；极小元类似定义

Dilworth定理

一个偏序集的最大反链长度等于其最小链覆盖；一个偏序集的最大链长度等于其最小反链覆盖

显然，前一分句和后一分句是等价的，下面证明前一分句：

考虑数学归纳法，设 $\mid A \mid \le m$ 时定理成立，下面证明 $\mid A \mid = m + 1$ 时定理也成立

设 $x$ 是一个极大元，则 $A’ = A - \{x\}$ 是满足定理的，设 $A’$ 的最小链覆盖为 $\{C_1, C_2, …, C_k\}$ ，而 $A’$ 中大小为 $k$ 的反链有 $S_1, S_2, …, S_r$ ，显然 $S_i$ 中包含$C_{1 \sim k}$ 各一个元素

现在考虑加入 $x$ 到集合 $A’$ ：

  • 最大反链长度和最小链覆盖都没变：显然定理仍然成立
  • 最大反链长度 $+1$ ：新的最大反链一定是 $x$ 与原来的最大反链构成的，可得 $x$ 与 $C_{1 \sim k}$ 中任意一个元素都不可比，那么 $C_{1 \sim k}$ 中没有一个链有机会覆盖 $x$ ，只能 $x$ 独立作为一个链覆盖，则最小链覆盖数 $+1$ ，定理仍然成立
  • 最小链覆盖数 $+1$ ：类似最大反链 $+1$ 可证

综上 $\mid A \mid = m + 1$ 时定理仍然成立，而 $\mid A \mid \le 1$ 时定理显然成立，故定理得证

直接运用

最经典的就是导弹拦截了

这是一个关于时间和高度的二维偏序，其实就是询问最大链长度和最小链覆盖数；第一问优化 dp 可做，第二问转化为最长反链长度（就是最长上升子序列），代码就不给了

与图论结合

在 DAG 中， Dilworth 有大用处：考虑把 $A$ 中每个元素对应为一个点， $x \preceq y$ 就对应一条有向边 $x \to y$ ，这样偏序集 $<A, \preceq>$ 就对应上了一个 DAG ，反过来，对于一个 DAG ，我们做一次传递闭包，它就对应一个偏序集

这里有一个建图的小技巧（？），由于 $\preceq$ 具有传递性，有时候不必一一加边（主要是我们比较两个元素 $x, y$ 的复杂度过大的时候），可以加部分边后传递闭包

建出图有啥用呢？发现建好图后，偏序中的链就变成了一个点集，其中任意两点要么有边 $x \to y$ ，要么有边 $y \to x$，而反链就变成了一个点集，其中任意两点之间无边，运用 Dilworth 定理，这两种点集就可以互相转化，发现反链对应的点集不就是最大独立集吗，而在做传递闭包之前，反链就对应着一个互相不可达的点的集合，要是可以求出最小链覆盖，这个 DAG 的最大独立集不就搞定了吗，也就是说，我们把最大独立集变成了最小链覆盖；再考虑链对应的点集，发现它对应最小路径覆盖，因为一条链上两点一定直接联通（注意我们已经传递闭包了），那么一条链一定对应一条路径（顺便一提，这里也给出了一种求最小可重复路径覆盖的思路，那就是传递闭包后变成最小不重复路径覆盖）；最后，对于 DAG 最小不重复路径覆盖有个定理： DAG 的最小无重复路径覆盖大小等于总点数减去拆点二分图的最大匹配数，其中拆点二分图的构造如下：将原图每个点分裂为两个点 $x, x’$ ，若原图中有边 $x \to y$ 则在拆点图中连边为 $x \to y’$

简单证明这个定理：先把每个点作为一个路径，显然就有总点数那么多的路径，然后我们考虑合并一些路径，同时保证一个点最多有一条出边一条入边，这对应到拆点图上就是匹配，那么我们每匹配上一组就有两条路径合并，所以最后最小无重复路径覆盖大小就等于总点数减去拆点二分图的最大匹配数

总结一下我们的转化思路：
$$
\begin{aligned}
& 原图中最大的互相不可达的点集 \\
\overset{传递闭包}{- \! \! \! \longrightarrow} & 新图中最大独立集 \\
= & 新图中最长反链 \\
\overset{Dilworth定理}{- \! \! \! -\! \! \! - \! \! \! - \! \! \! - \! \! \! \longrightarrow} & 新图中的最小链覆盖 \\
= & 新图中的最小路径覆盖 \\
\overset{某不知名定理}{- \! \! \! - \! \! \! - \! \! \! \longrightarrow} & 总点数 - 拆点图最大匹配
\end{aligned}
$$
（这可真绕）

例题

那么现在就该用用这玩意了，看这个

Birthday

题目大意

给定 $n \le 750$ 个字符串组成的集合 $S$ ，保证 $S$ 中元素两两不同，求 $S$ 的最大的一个子集满足其中任意一个字符串不是另一个字符串的子串，保证所有字符串长度和 $\mid S \mid \le 10^7$ ，要求构造出方案

思路

首先“子串”显然也是一个偏序，问题是如何求出这 $n$ 个串的偏序关系，考虑 AC 自动姬（当然用 SAM 也可），对 $S$ 中所有串建出 AC 自动机后尝试从每个点向上跳，显然每次把 fail 指针跳完时间会爆炸，我们每次只找到第一个存在的字符串（由 fail 指针的性质，这个串一定是最长的）并且类似并查集搞一个路径压缩

然后就是上面的套路了，传递闭包变成最小路径覆盖，拆点做最大匹配

现在问题在于构造方案，先把最大匹配方案找到，然后由此得到最小路径覆盖的方案，接下来我们要从每条路径里面选一个点作为最长反链，具体的：

  1. 取出所有终点，构成集合 $E$
  2. 从 $E$ 中所有点正向走一条边，走到的点集记作 $ne(E)$ ，若 $E \cap ne(E) = \varnothing$ ，则 $E$ 即为所求
  3. 否则，对于所有 $e \in E \cap ne(E)$ ，反向走至 $e’ \notin ne(E)$ ，在 $E$ 中将 $e$ 换成 $e’$
  4. 再次回到步骤 $2$

总时间复杂度为 $O(\mid S \mid + n^3)$ ，瓶颈是 ACAM 和 Floyd 所直接用匈牙利求匹配就好（当然你想卡常用网络流也行）

然后你会发现字符集仅包含 $a, b$ 这个性质从头到尾没用，没准这是为了保证时空常数小？

代码

这题空间卡的有点紧，据说递归深了会爆栈，所以 AC 自动机上跳过程我们找一个栈来存中间的点

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
#include <bits/stdc++.h>
const int N = 750 + 50, L = 1e7 + 100;
int n, pos[N], stk[L], top, ans, lk[N];
char s[L];
bool d[N][N], vis[N];
bool dfs(int x)
{
	for (int i = 1; i <= n; ++i) if (d[x][i] && !vis[i])
	{
		vis[i] = true;
		if (!lk[i] || dfs(lk[i])) return lk[i] = x, true;
	}
	return false;
}
struct ACAM
{
	int tot, ch[L][2], fail[L], fa[L], ed[L];
	ACAM() : tot(1) {}
	int ins(char *s, int id)
	{
		int p = 1;
		while (*s)
		{
			int c = *s++ - 'a';
			if (!ch[p][c]) ch[p][c] = ++tot, fa[tot] = p;
			p = ch[p][c];
		}
		ed[p] = id;
		return p;
	}
	void bd()
	{
		std::queue<int> q;
		for (int i = 0; i < 2; ++i)
			if (ch[1][i]) fail[ch[1][i]] = 1, q.push(ch[1][i]);
			else ch[1][i] = 1;
		while (!q.empty())
		{
			int x = q.front(); q.pop();
			for (int i = 0; i < 2; ++i)
				if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
				else ch[x][i] = ch[fail[x]][i];
		}
	}
} ac;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", s + 1);
		pos[i] = ac.ins(s + 1, i);
	}
	ac.bd();
	for (int i = 1; i <= n; ++i)
		for (int j = pos[i]; j != 1; j = ac.fa[j])
		{
			int x = ac.fail[j];
			stk[top = 1] = j;
			while (!ac.ed[x] && x != 1) stk[++top] = x, x = ac.fail[x];
			while (top) ac.fail[stk[top--]] = x;
			if (j != pos[i] && ac.ed[j]) x = j;
			if (ac.ed[x]) d[i][ac.ed[x]] = true;
		}
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j) d[i][j] |= d[i][k] & d[k][j];
	for (int i = 1; i <= n; ++i) d[i][i] = false;
	ans = n;
	for (int i = 1; i <= n; ++i)
	{
		ans -= dfs(i);
		std::memset(vis, false, (n + 1) * sizeof(bool));
	}
	for (int i = 1; i <= n; ++i) vis[lk[i]] = true;
	top = 0;
	for (int i = 1; i <= n; ++i) if (!vis[i]) stk[++top] = i;
	std::memset(vis, false, (n + 1) * sizeof(bool));
	for (bool find = false; !find; )
	{
		find = true;
		for (int *x = stk + top; x != stk; --x)
			for (int y = 1; y <= n; ++y) if (d[*x][y]) vis[y] = true;
		for (int *x = stk + top; x != stk; --x) if (vis[*x])
		{
			while (vis[*x]) *x = lk[*x];
			find = false;
		}
	}
	printf("%d\n", ans);
	for (int i = 1; i <= top; ++i) printf("%d ", stk[i]);
	return 0;
}