[BZOJ1143][CTSC2008]祭祀river(Dilworth定理+二分图匹配)

题意：给你一张n个点的DAG，最大化选择的点数，是点之间两两不可达。

要从Dilworth定理说起。

Dilworth定理是定义在偏序集上的，也可以从图论的角度解释。偏序集中两个元素能比较大小，则在图中连一条有向边。

定义反链为一个点集，满足集合中的点两两不可达。

Dilworth定理：最小路径覆盖=最长反链。

证明：http://vfleaking.blog.163.com/blog/static/1748076342012918105514527/

例子：NOIP1999第二问：给定一个数列a，将其分成若干个子序列，使每个子序列都是下降子序列，并最小化分的子序列个数。

对于所有i<j且a[i]>a[j]，从i向j连边，则问题转化成求图的最小路径覆盖，根据Dilworth定理进一步转化为求最长反链，而这里的最长反链即是最长不降子序列的长度。所以这题只要求一个最长不降子序列即可。

回到这道题，就是要求一个最长反链。这里任意两个可达的点之间都需要连一条边，所以需要求传递闭包。

然后通过Dilworth定理转化为求DAG的最小路径覆盖，这就是二分图匹配的经典问题了。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=;

 int n,m,u,v,ans,lk[N];

 bool mp[N][N],a[N][N],vis[N];

 bool find(int x){

     rep(i,,n) if (!vis[i] && mp[x][i]){

         vis[i]=;

         if (!lk[i] || find(lk[i])) { lk[i]=x; return ; }

     }

     return ;

 }

 int main(){

     freopen("bzoj1143.in","r",stdin);

     freopen("bzoj1143.out","w",stdout);

     scanf("%d%d",&n,&m);

     rep(i,,m) scanf("%d%d",&u,&v),mp[u][v]=;

     rep(k,,n) rep(i,,n) rep(j,,n) mp[i][j]|=mp[i][k]&mp[k][j];

     rep(i,,n) rep(j,,n) if (i!=j && mp[i][j]) a[i][j]=;

     rep(i,,n){

         memset(vis,,sizeof(vis));

         if (find(i)) ans++;

     }

     printf("%d\n",n-ans);

     return ;

 }