最大匹配:最大的任意点最多只被一条边覆盖的边集。
最小点覆盖:最小的任意边都至少有一个端点被覆盖的点集。
最小链覆盖:最小的任意点都被覆盖的不存在相交链的链集。
最长反链:最大的任意两点相互不可达的点集。
最大独立集:最大的生成子图为空集的点集。
懒得证明了,下面将给出由最大匹配构造最小点覆盖的方法。
我们知道匈牙利算法中要寻找的增广路是一条边在当前匹配,下一条边不在当前匹配,且起点和终点都未被覆盖的路径。
在起点集中枚举每一个未被最大匹配覆盖的点,从这个点出发找到以其为起点的所有增广路,并标记路上的所有点。
最后起点集中未被标记的点和终点集中被标记的点就是最小点覆盖。
证:把最小点覆盖去掉后,一定不存在两个端点都未被去掉的边,因此剩下的就是最大独立集。
伪证:最大匹配中的边\(u,v\)就相当于把原图中的\(u,v\)两个点缩成一个点,所以最后剩下的点数即最小链覆盖数等于总点数减最大匹配数。
懒得证了,下面给出构造方法。
设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