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

· · 算法·理论

注：文中的偏序集用一个 DAG 的形式描述。

给你个偏序集，要求最长反链的长度。这是一个经典问题。

要你把最长反链构造出来呢，怎么办？

参考文献

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

二分图最大独立集

我们知道，一个二分图的最小点覆盖等于最大匹配，原因在下面。

我们要先求得二分图的一个最大独立集，也就是点覆盖的补集。

先随便求一个最大匹配。

考虑以下 dfs 过程：从每一个右部非匹配点出发，右 \to 左只非走匹配边，左 \to 右只走匹配边。

最小点覆盖，就是左边遍历到的结点集合，和右边没遍历到的结点集合的并集。

点覆盖构造的证明

假设我们得到的点集为 S，二分图最大匹配为 m。

  1. 所以这个事情告诉我们，每条匹配边一定有恰好一个端点被选。由于匹配的端点两两不重复，所以 $|S| \ge m$。
  3. 每条边都被覆盖。考虑反证，假设有一条边没被覆盖，那么左端点没被 dfs 过，右端点被 dfs 过了。由于做短点没被 dfs 过，因此这个右端点一定是非匹配点。然而非匹配点连出的边一定是非匹配边，因此它的每个邻居都应当遍历过，矛盾。

同时我们也能证明上面说的“二分图的最小点覆盖等于最大匹配”的结论，因为每条匹配边至少都要选一个端点，所以 |S| \ge m，同时我们能构造出 |S| = m 的方案，因此一定有最小点覆盖等于最大匹配，同时说明了我们构造的方案是最小点覆盖。

最长反链的长度

这个是比较简单且经典的。

根据 Dilworth 定理，偏序集上最长反链长度 = 最小链覆盖数。

一开始每个点都是散点，我们想要通过合并尽可能多次形成尽可能少的链。

那么我们把每个点 i 拆成出点和入点 i_1, i_2，当前点的出点连向所有可能的后继的入点，所有可能的前驱的出点连向当前点的入点。这样会形成一个二分图。

那么每个点在链上前驱后继至多各一个，所以合并次数就是这个二分图的最大匹配。

最小链覆盖数 = n - 最大匹配。

构造最长反链

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

最长反链构造的证明

先证明这是一个反链。

考虑反证，假设存在 u, v 在构造中且 u \to v 有连边。那么 u_2 \to v_1 在二分图上有连边，和 u_1, u_2, v_1, v_2 都属于独立集相矛盾。

再考虑证明这是最长的。

假设二分图左、右点数均为 n。那么最大独立集大小 |S|= 2n - m。

又因为最大独立集大小为

之和。

容易发现第二个 |S_2| \le n。所以 |S_1| \ge |S| - |S_2| = n-m！

最长反链的长度就是 n-m，我们得到了合法的构造。

实现

P4298 部分代码。

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，是个类似的题。