【笔记】Dilworth定理

给定一个有向无环图，我们称 \(x,y\) 存在关系当且仅当存在 \(x\to y\) 或者 \(y \to x\) 的边。最长链为最大的集合使得其中任意两个元素存在关系，最长反链为最大的集合使得其中任意两个元素不存在关系。

Dilworth 定理：最长反链等于最小链覆盖。

最小链覆盖为用最少的链（可以相交）覆盖图的每一个点，我们传递闭包后即可转化为经典二分图模型：最小链划分。

如何求出具体方案？我们先求出链划分，然后先选取每条链的终点，只要存在两个点之间有关系，如 \(x\to y\)，就将 \(y\) 沿着对应的链向起点走。可以证明重复这个过程可以得到答案。

听起来很复杂，但实现很简单。下面是 CF590E 的代码。

#define N 10000005 #define M 755 char s[N + M]; int idx, n, ch[N][2], fa[N], w[N], u[M], d[M][M], m, v[M], mat[M]; queue<int>q; bool dfs(int x){ 	rp(i, n)if(d[x][i] && !v[i]){ 		v[i] = 1; 		if(!mat[i] || dfs(mat[i])){mat[i] = x; return true;} 	}return false; } vector<int>c; int main() { 	read(n); 	rp(i, n){ 		u[i] = ++m; scanf(%s, s + m); 		int l = strlen(s + m), x = 0; 		rp(j, l){ 			int op = s[j + m - 1] - 'a'; 			if(!ch[x][op])ch[x][op] = ++idx; 			x = ch[x][op]; 		} 		w[x] = i, m += l; 	} 	if(ch[0][0])q.push(ch[0][0]); 	if(ch[0][1])q.push(ch[0][1]); 	while(!q.empty()){ 		int x = q.front(); q.pop(); 		if(!w[x])w[x] = w[fa[x]]; 		if(ch[x][0])fa[ch[x][0]] = ch[fa[x]][0], q.push(ch[x][0]); 		else ch[x][0] = ch[fa[x]][0]; 		if(ch[x][1])fa[ch[x][1]] = ch[fa[x]][1], q.push(ch[x][1]); 		else ch[x][1] = ch[fa[x]][1]; 	} 	rp(i, n){ 		int k = strlen(s + u[i]), x = 0; 		rp(j, k){ 			if(w[x])d[i][w[x]] = 1; 			x = ch[x][s[j + u[i] - 1] - 'a']; 		} 		if(w[fa[x]])d[i][w[fa[x]]] = 1; 	} 	rp(k, n)rp(i, n)rp(j, n)d[i][j] |= d[i][k] & d[k][j]; 	int ans = n; 	rp(i, n){ 		memset(v, 0, sizeof(v)); 		if(dfs(i))ans--; 	} 	printf(%d\n, ans); 	memset(v, 0, sizeof(v)); 	rp(i, n)v[mat[i]] = 1; 	rp(i, n)if(!v[i])c.pb(i); 	while(true){ 		memset(v, 0, sizeof(v)); 		go(x, c)rp(i, n)if(d[x][i])v[i] = 1; 		int p = 0; 		for(auto &x : c)while(v[x])x = mat[x], p = 1; 		if(!p)break; 	} 	go(x, c)printf(%d , x);el; 	return 0; }