首页 > 其他 > 详细

最长反链

时间:2019-10-17 00:35:26      阅读:70      评论:0      收藏:0      [点我收藏+]

定义:

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

定理一(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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!