最长反链

定义：

最大匹配：最大的任意点最多只被一条边覆盖的边集。
最小点覆盖：最小的任意边都至少有一个端点被覆盖的点集。
最小链覆盖：最小的任意点都被覆盖的不存在相交链的链集。
最长反链：最大的任意两点相互不可达的点集。
最大独立集：最大的生成子图为空集的点集。

定理一(Konig定理)：二分图的最小点覆盖数等于其最大匹配数。

懒得证明了，下面将给出由最大匹配构造最小点覆盖的方法。
我们知道匈牙利算法中要寻找的增广路是一条边在当前匹配，下一条边不在当前匹配，且起点和终点都未被覆盖的路径。
在起点集中枚举每一个未被最大匹配覆盖的点，从这个点出发找到以其为起点的所有增广路，并标记路上的所有点。
最后起点集中未被标记的点和终点集中被标记的点就是最小点覆盖。

定理二：二分图的最大独立集为最小点覆盖的补集。

证：把最小点覆盖去掉后，一定不存在两个端点都未被去掉的边，因此剩下的就是最大独立集。

定理三：一个DAG的最小链覆盖数等于总点数\(n\)减去其对应二分图（建立两个大小为\(n\)的点集\(X,Y\)，对于原图中的边\(u,v\)，我们在二分图中建边\(X_u,Y_v\)）的最大匹配数。

伪证：最大匹配中的边\(u,v\)就相当于把原图中的\(u,v\)两个点缩成一个点，所以最后剩下的点数即最小链覆盖数等于总点数减最大匹配数。

定理四(Dilworth定理)：DAG的最长反链数等于最小链覆盖数。

懒得证了，下面给出构造方法。
设DAG有\(n\)个点，其最大匹配数为\(m\)。
先构造出DAG的二分图，求出其最大独立集。
然后如果\(X_i,Y_i\)都在独立集中，我们就将其加入反链。
首先这东西显然是个反链对吧。
然后这个独立集的大小为\(2n-m\)，独立集的大小等于反链大小加上\(X_i,Y_i\)有一个在独立集中的点数，后面这个东西显然\(\le n\)，所以反链大小\(\ge n-m\)。
然后由Dilworth定理，我们知道反链大小一定为\(n-m\)。

最小链覆盖例题：

Luogu P2764 最小路径覆盖问题
题目

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=151;
vector<int>E[N];int vis[N],T,mat[N],a[N];deque<int>q[N];
int dfs(int u)
{
    for(int v:E[u])
    if(vis[v]^T)
    {
        vis[v]=T;
        if(!mat[v]||dfs(mat[v])) return mat[v]=u;
    }
    return 0;
}
int read(){int x;cin>>x;return x;}
int main()
{
    int n=read(),m=read(),i,j,u,v,c=0,f;
    for(i=1;i<=m;++i) u=read(),v=read(),E[u].pb(v);
    for(i=1;i<=n;++i) ++T,dfs(i);
    for(i=1;i<=n;++i)
    {
    if(!mat[i]) continue;
    for(f=0,j=1;!f&&j<=c;++j)
    {
        if(q[j].back()==mat[i]) q[j].push_back(i),f=1;
        if(q[j].front()==i) q[j].push_front(mat[i]),f=1;
    }
    if(!f) q[++c].push_back(mat[i]),q[c].push_back(i);
    }
    for(i=1;i<=c;puts(""),++i) while(!q[i].empty()) a[q[i].front()]=1,printf("%d ",q[i].front()),q[i].pop_front();
    for(i=1;i<=n;++i) if(!a[i]) printf("%d\n",i),++c;
    printf("%d",c);
}

最长反链

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/11688296.html