注意在有向无环图中。链是一个点的集合。这个集合中任意两个元素x y 要么x能走到y 要么y能走到x。
反链也是一个点的集合不过在这个点集之中 其中任意两个元素 x,y 谁都不能走到谁。
最长反链如何求出？根据某个啥啥定理来说最长反链==最小链覆盖数 最小链覆盖 是指 用最少的链经过所有点至少一次。
对于这个定理的证明我们有更简洁的方法：最小链覆盖==最大独立集数 这个显然因为最后的答案求出的方法是一模一样的。
注意此时我们已经转换成了二分图 经过最小链覆盖的转换 因为这张二分图是经过连通性（传递闭包）传递过的 这样做的原因是 最少的链经过所有点至少一次 我们对于任意的匹配都可以认为是 一整个链都覆盖上了以至于匹配上了所有的点。故最大独立集实在转后后的二分图上做的而并非是在原图上做的 原图我怎么看都不是二分图...
在证明之前 设 n为这张图上的点数 而 二分图中的点数为2n 设此图的最大匹配数为m
考虑构造。 最长反链究竟是一个怎样的集合呢？我们考虑在求最大独立集的过程 我们取点的时候从左部未匹配的点开始跑标记 把左部和右部点都标记 此时我们取左部未标记点 右部已标记。
那么 这些点 就是最小点覆盖 最大独立集陷入就是左部被标记点和右部未被标记点 此时我们最长反链==x 当前仅当 x属于左部被标记点和右部未被标记点我们论述一下这个集合必然是反链的集合。
对于这个集合中的x 和y 来说 因为x 和y都是属于最大独立集中的点 根据我们开始跑的连通性 他们一定没有边相连 故这个集合必然是反链的集合。
考虑最大独立集(2n-m)==反链集合+x属于左边被标记点或x属于右边被标记点 显然的是后者最多有n个故前者最少有 2n-m-n=n-m个。
也就是说最长反链集合至少为n-m 由于最小链覆盖的大小是n-m 故最长反链<=n-m 故这个反链的大小为n-m 即我们要求的最长反链。
考虑一个点是否可以在最长反链之中 把能到这个点的点和这个点能到的点及这个点删掉 再求出最长反链看反链大小是否-1 如果减一了说明此点在最长反链之中如果答案没有-1说明了这个点是不必要的 其不属于最长反链之中。
例题 CTSC 2008 祭祀 锣鼓 P4298
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<ctime> #include<cstring> #include<string> #include<ctime> #include<cctype> #include<cstdio> #include<utility> #include<queue> #include<stack> #include<deque> #include<map> #include<set> #include<bitset> #include<vector> #include<algorithm> #include<cstdlib> using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=110; int n,m,cnt,ans,ans1; int a[MAXN][MAXN],w[MAXN]; int match[MAXN],vis[MAXN],c[MAXN]; inline void floyd() { for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]|=a[i][k]&a[k][j]; } inline int dfs(int x) { if(w[x])return 0; vis[x]=cnt; for(int i=1;i<=n;++i) { if(w[i])continue; if(!a[x][i])continue; if(!match[i]||(vis[match[i]]!=cnt&&dfs(match[i]))) { match[i]=x;c[x]=i; return 1; } } return 0; } inline void gz(int x) { if(vis[x])return; vis[x]=1; for(int i=1;i<=n;++i) { if(a[x][i]&&!w[i])w[i]=1,gz(match[i]); } } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=m;++i) { int x,y; x=read();y=read(); a[x][y]=1; } floyd(); for(int i=1;i<=n;++i) { ++cnt; if(dfs(i))++ans; } printf("%d ",ans1=(n-ans)); //最长反链 memset(vis,0,sizeof(vis)); memset(w,0,sizeof(w)); for(int i=1;i<=n;++i)if(!c[i])gz(i); for(int i=1;i<=n;++i)printf("%d",vis[i]&&!w[i]); puts(""); for(int i=1;i<=n;++i) { memset(w,0,sizeof(w)); int s=n; for(int j=1;j<=n;++j) { if(a[i][j])w[j]=1,--s; if(a[j][i])w[j]=1,--s; } w[i]=1;--s;cnt=0;ans=0; memset(match,0,sizeof(match)); for(int j=1;j<=n;++j) { ++cnt; if(dfs(j))++ans; } if(ans1-1==s-ans)printf("%d",1); else printf("%d",0); } return 0; }