前置知识

偏序集

要谈偏序集,首先要有一个比较关系.这个关系可以使两个元素进行比较.最典型的就是定义在整数集上的小于等于号\leq,它就代表着一个二元关系.

偏序集就是元素的集合加上比较关系,同时还要满足如下三条性质:

1. 自反性: \forall a \in S,a \leq a
2. 对称性: \forall a,b \in S,若a \leq b,则b \geq a
3. 传递性: 若a \leq b,b \leq c,则a \leq c

注意:偏序集中的元素是可以不可比的.

如果说对于每个a,b,若a \leq b,连上一条a -> b的边,整个集合就可以转化为一个DAG图,然后就可以在这个图上研究偏序集的性质了.

链划分

又称链覆盖.首先要明确链的概念:链是一些元素构成的集合,这个集合中的元素两两可比.

可以简单理解为一个DAG图上一条路径的一部分.也就是这些点是可以不连续的.

链划分,或者说链覆盖,就是把整个偏序集的元素划分到一些链上.每个元素属于且只属于一条链,也就是链之间不相交.

显然,最小链划分就是划分出链的数目最少的那种划分方式.

反链

和链的定义相反,反链的定义是:一些元素构成的集合,这个集合中的元素两两不可比.

放到DAG图上来看就是,这个集合中的点,两两之间不可到达.

定理内容

讲了那么多,终于要搬出Dilworth定理了.Dilworth定理的内容如下:

偏序集上最小链划分中链的数量等于其反链长度的最大值。

在有前置知识的情况下看着比较像人话了

证明比较繁琐,直观上可以理解为从每个链划分中取一个元素出来,就可以构成反链了.

当然只有定理是不行的,最起码要能够求出反链长度或者最小链划分数才有意义.所以还要再引入如下定理:

DAG图最小链覆盖数等于原图点数-拆点后的二分图最大匹配数

拆点后的新图构造规则如下:

每一个点拆为上下两个分点,记为x_{1}和x_{2}对于点对x,y,若有x->y,则连边x_{1}->y_{2}.这样就得到了一个二分图,就可以计算最大匹配数了.

证明:把一开始的所有点都看做是一条路径.当完成了一个匹配后,就相当于这两条路径合并为了一条.拆点这一处理保证了一个点至多会位于一条路径中.所以最小路径覆盖就等于点数-匹配数.

有了上面两个定理,就可以通过网络流快乐地求一个偏序集的最长反链了.

应用

Algorithm Teaching(Codeforces Gym)

题意

有n个集合,每个集合中有一些元素.现在要求从这些集合的所有非空子集构成的大集合中,选出一个最大的子集,使得这个子集中的任意两个小集合都没有包含关系.

题解

集合的包含关系就是一个典型的偏序关系.集合+包含关系就可以构成偏序集.

知道了Dilworth定理后,不难看出这个题就是让求一个最长反链.通过上面的定理转化为二分图跑网络流就可以了.

代码

#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#define IL inline
#define reg register
#define LL long long
#define N 110
#define NM 500010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,j,k,tot,sum,cnt=1,lsum=1,Found,al,flow;
int a[N][N],head[NM],id[N*N],up[NM],down[NM];
int gaps[NM],gap[NM],cur[NM];
string c;

bitset <1010> v[2020];

map <string,int> M,P;

struct Flow{
    int t,next,fl,re;
}e[NM*8];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL void FAST_IO() {ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);}

IL void Add(int s,int t,int fl){
    e[lsum].t=t;    e[lsum].fl=fl;  e[lsum].next=head[s];   e[lsum].re=lsum+1;  head[s]=lsum++;
    e[lsum].t=s;    e[lsum].fl=0;   e[lsum].next=head[t];   e[lsum].re=lsum-1;  head[t]=lsum++;
}

IL int Get_ID(int x,int p){
    if (!p && up[x])    return up[x];
    if (p && down[x])   return down[x];
    if (!p){
        up[x]=x+1;  cnt++;  return x+1;
    }   else {
        down[x]=x+1+200000; cnt++;  return down[x];
    }
}

inline void Sap(int x){
    int F=al,i=0,mingap=cnt-1;
    if (x==cnt) {Found=1;   flow+=al;   return;}
    for (i=cur[x];i;i=e[i].next)
    if (e[i].fl){
        if (gap[e[i].t]+1==gap[x]){
            al=Min(al,e[i].fl); Sap(e[i].t);
            if (gap[1]>=cnt)    return;
            if (Found)  {cur[x]=i;  goto END;}
            al=F;
        }
        mingap=Min(mingap,gap[e[i].t]);
    }
    for (i=head[x];i!=cur[x];i=e[i].next)
    if (e[i].fl){
        if (gap[e[i].t]+1==gap[x]){
            al=Min(al,e[i].fl); Sap(e[i].t);
            if (gap[1]>=cnt)    return;
            if (Found)  {cur[x]=i;  break;}
            al=F;
        }
        mingap=Min(mingap,gap[e[i].t]);
    }
    END:
    if (!Found){
        gaps[gap[x]]--; if (!gaps[gap[x]])  gap[1]=cnt;
        gaps[gap[x]=mingap+1]++;    cur[x]=head[x];
    }   else e[i].fl-=al,e[e[i].re].fl+=al;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    FAST_IO();
    cin>>n;
    for (i=1;i<=n;i++){
        cin>>m;
        for (j=1;j<=m;j++){
            cin>>c;
            if (M[c])   a[i][j]=M[c];
            else 
                a[i][j]=M[c]=++tot;
        }

        for (j=1;j<(1<<m);j++){
            v[j].reset();
            for (k=0;k<m;k++)
                if (j&(1<<k))   v[j][a[i][k+1]]=1;
            c=v[j].to_string();
            if (P[c])   id[j]=P[c];
            else id[j]=P[c]=++sum;
        }

        for (j=1;j<(1<<m);j++)
            for (k=0;k<m;k++)
                if (j&(1<<k))
                    Add(Get_ID(id[j],0),Get_ID(id[j^(1<<k)],1),1);
    }
    cnt++;
    for (i=1;i<=sum;i++)    Add(1,up[i],1),Add(down[i],cnt,1);
    gaps[0]=cnt;
    while (gap[1]<cnt){
        Found=0;    al=INF; Sap(1);
    }
    cout<<sum-flow<<endl;
    return 0;
}

参考资料

偏序集的最大反链【二分图】

浅谈Dilworth定理