Dilworth 定理/反链定理

Dilworth 定理/反链定理

二元组：（a,b），图G=(V,E)，E为二元组。

二元关系：二元组构成的集合，如E。如果(a,b)有关系，那么(a,b)在R中，如果没有关系，那么就不在R里。

偏序关系：二元关系R。满足：

1. 自反性。\((a,a)\in R\)
2. 反对称性。\((a，b)\in R,(b,a)\in R\Rightarrow a=b\)
3. 传递性。\((a,b)\in R,(b,c)\in R\Rightarrow (a,c)\in R\)
4. 可以存在 \((a,b)\notin R,(b,a) \notin R\)。如果任意满足则称为全序关系。

前缀属于偏序关系。对于字符串，如果 \(a\) 是 \(b\) 的前缀，则 \((a,b)\in R\)。子集，整除，小于等于等属于偏序关系。

偏序关系是DAG的传递闭包，因为有传递性。可以用DAG来表示。

链:集合 \(S\)，满足对于任意 $\forall x,y\in S,(x,y)\in R $ 或 \((y,x)\in R\)。对应DAG上一条路径。

反链：集合 \(T\)，满足对于 $\forall x,y\in T（x\neq y）,(x,y)\notin R $ 且\((y,x)\notin R\)。反链对应DAG的一个独立集，即任何两个点没有边。这里说的DAG都是加上了传递后的边。

a b
b e
b c
f b
c g
c d

Dilworh 定理

最小链覆盖等于最长反链。

最小链覆盖指的是最少条链来覆盖整张DAG。集合大小相等。

题型

要求最小链覆盖

转化为最长反链，使用DP求解。

求最长反链

转化为最小链覆盖，用网络流求解。

P1020

导弹 \((i,a_i)\) 放入，二元关系为自反和 \(i<j\) and \(a_i\geq a_j\)。反链为 \(i<j,a_i<a_j\)

P3974

\((i,j)\) 有 \(a_{i,j}\) 个地雷，求多少次全部扫完。

拆成 \((i,j,k),1\leq k\leq a_{i,j}\)
二元关系：

1. \((i_1,j_1,k_1)(i_2,j_2,k_2)\)，若 \((i_1,j_1)=(i_2,j_2)\)，\(k_1=k_2\) 有关系，\(k_1\neq k_2\) 无关系。否则若 \(i_1\leq j_1,j_1\leq j_2\)，那么有关系。

反链为 \((i_1,j_1)=(i_2,j_2)\) 或 \((i_1>i_2且j_1<j_2)\)。

\[f(i,j)=f(i+1,j-1)+a_{i,j} \]

\[f(i+1,j),f(i,j-1) \]

P4298

拆点，答案为 \(n-最大匹配\)。构造方案:

1. 暴力。枚举每一个点，删掉，检查最小链覆盖是否减少1，就说明这个点是不可以。
2. 使用Dinic，对于一个 \(x\)，若从 \(S\) 开始 dfs 能搜到 \(x\)，称 \(x\in S\)，否则 \(x\in T\)。存在一个方案,\(x\in方案\) 当且仅当 \(x_o\in S\),\(x_i\in T\)。