专栏文章

怎么求一个偏序集的最长反链并构造方案？

ddyc2022
算法·理论参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mkh4lx40
此快照首次捕获于
2026/01/17 01:02
上个月
此快照最后确认于
2026/02/19 01:17
10 小时前
查看原文
注：文中的偏序集用一个 DAG 的形式描述。
给你个偏序集，要求最长反链的长度。这是一个经典问题。
要你把最长反链构造出来呢，怎么办？

参考文献

https://r-64.blog.uoj.ac/blog/623
https://www.luogu.com.cn/article/05a58z7z

二分图最大独立集

我们知道，一个二分图的最小点覆盖等于最大匹配，原因在下面。
我们要先求得二分图的一个最大独立集，也就是点覆盖的补集。
先随便求一个最大匹配。
考虑以下 dfs 过程：从每一个右部非匹配点出发，右 →\to 左只非走匹配边，左 →\to 右只走匹配边。
最小点覆盖，就是左边遍历到的结点集合，和右边没遍历到的结点集合的并集。

点覆盖构造的证明

假设我们得到的点集为 SS，二分图最大匹配为 mm。
  1. ∣S∣≥m|S| \ge m：我们考虑右侧的点。右侧的非匹配点一定 dfs 过所以没选，因此选的点都是匹配点。对于一个匹配点，如果它不选，那么它一定被 dfs 过，而它的前驱是唯一的，是与它匹配的某个左侧的点。
    所以这个事情告诉我们，每条匹配边一定有恰好一个端点被选。由于匹配的端点两两不重复，所以 ∣S∣≥m|S| \ge m。
  2. ∣S∣=m|S| = m：我们考虑左边的一个非匹配点。如果它被 dfs 到了，那么我们就找到了一条从非匹配点出发，重复走过左右两边，在非匹配点结束的路径，也就是找到了一个增广路，和最大匹配违背。因此有且仅有匹配边的端点被选到，且每条边恰好选择一个端点。
  3. 每条边都被覆盖。考虑反证，假设有一条边没被覆盖，那么左端点没被 dfs 过，右端点被 dfs 过了。由于做短点没被 dfs 过，因此这个右端点一定是非匹配点。然而非匹配点连出的边一定是非匹配边，因此它的每个邻居都应当遍历过，矛盾。
同时我们也能证明上面说的“二分图的最小点覆盖等于最大匹配”的结论，因为每条匹配边至少都要选一个端点，所以 ∣S∣≥m|S| \ge m，同时我们能构造出 ∣S∣=m|S| = m 的方案，因此一定有最小点覆盖等于最大匹配，同时说明了我们构造的方案是最小点覆盖。

最长反链的长度

这个是比较简单且经典的。
根据 Dilworth 定理，偏序集上最长反链长度 = 最小链覆盖数。
一开始每个点都是散点，我们想要通过合并尽可能多次形成尽可能少的链。
那么我们把每个点 ii 拆成出点和入点 i1,i2i_1, i_2，当前点的出点连向所有可能的后继的入点，所有可能的前驱的出点连向当前点的入点。这样会形成一个二分图。
那么每个点在链上前驱后继至多各一个，所以合并次数就是这个二分图的最大匹配。
最小链覆盖数 =n−= n - 最大匹配。

构造最长反链

我们考虑求出上述二分图的最大独立集。假设最大独立集中左部点选择的集合为 LL，右部点选择的集合为 RR。我们声称，在我们的构造中 ii 在这个反链中必须满足 i1∈L∧i2∈Ri_1 \isin L \land i_2 \isin R。

最长反链构造的证明

先证明这是一个反链。
考虑反证，假设存在 u,vu, v 在构造中且 u→vu \to v 有连边。那么 u2→v1u_2 \to v_1 在二分图上有连边，和 u1,u2,v1,v2u_1, u_2, v_1, v_2 都属于独立集相矛盾。
再考虑证明这是最长的。
假设二分图左、右点数均为 nn。那么最大独立集大小 ∣S∣=2n−m|S|= 2n - m。
又因为最大独立集大小为
  • 满足 u1,u2u_1, u_2 同时在独立集中的点数 ∣S1∣|S_1|。
  • u1,u2u_1, u_2 有且只有一个在独立集中的点数 ∣S2∣|S_2|。
之和。
容易发现第二个 ∣S2∣≤n|S_2| \le n。所以 ∣S1∣≥∣S∣−∣S2∣=n−m|S_1| \ge |S| - |S_2| = n-m！
最长反链的长度就是 n−mn-m，我们得到了合法的构造。

实现

P4298 部分代码。
CPP
void dfs(int u) {vis[u]=1; for(int v:bG[u])if(!vis[v])dfs(v);}
main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++)
		scanf("%d%d",&u,&v),g[u].set(v);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)if(g[j][i])g[j]|=g[i];
	G.init(),G.s=n*2+1,G.t=n*2+2;
	for(int i=1;i<=n;i++)
		G.addflow(G.s,i,1),G.addflow(i+n,G.t,1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(g[i][j])G.addflow(i,j+n,1),id[i][j+n]=G.cnt-1;
	int ans=n-G.getflow(); printf("%d\n",ans);
	for(int i=1;i<=n;i++)
		for(int j=n+1;j<=n*2;j++)if(id[i][j])
			{if(G.E[id[i][j]].w)bG[i].push_back(j),mt[j]=1; else bG[j].push_back(i);}
	for(int i=n+1;i<=n*2;i++)if(!mt[i])dfs(i);
	for(int i=1;i<=n;i++)
		if(!vis[i]&&vis[i+n])putchar('1'); else putchar('0'); putchar(10);
	for(int i=1,new_ans;i<=n;i++)
	{
		new_ans=0;
		for(int j=1;j<=n;j++)
			flag[j]=(j!=i&&!g[i][j]&&!g[j][i]),new_ans+=flag[j];
		G.init(),G.s=n*2+1,G.t=n*2+2;
		for(int j=1;j<=n;j++)
			G.addflow(G.s,j,1),G.addflow(j+n,G.t,1);
		for(int j=1;j<=n;j++)if(flag[j])
			for(int k=1;k<=n;k++)if(flag[k]&&g[j][k])G.addflow(j,k+n,1);
		new_ans-=G.getflow();
		if(new_ans==ans-1)putchar('1'); else putchar('0');
	}
	return 0;
}
也可以去看看 SPOJ-DIVREL，是个类似的题。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...