bzoj 1143

求最长反链裸题

补充一点知识。。

　　链                  :    D 中的一个子集 C   满足 C 是全序集  及C中所有元素都可以比较大小

反链              :    D 中的一个子集 B   满足 B 中任意非空子集都不是全序集  即所有元素之间都不可以比较大小

链覆盖          :    若干个链的并集为 D ，且两两之间交集为 ∅

反链覆盖      :    若干个反链的并集为 D ，且两两之间交集为∅

最长链          :    所有链中元素个数最多的  (可以有多个最长链)

最长反链      :    所有反链中元素个数最多的 (可以有多个最长反链

偏序集高度  :    最长链的元素个数

偏序集宽度  :    最长反链中的元素个数

最长反链等于最小链覆盖， 最小链覆盖可以用二分图匹配求。

 #include<bits/stdc++.h>

 #define LL long long

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 using namespace std;

 const int N=+;

 const int M=1e4+;

 const int inf=0x3f3f3f3f;

 const LL INF=0x3f3f3f3f3f3f3f3f;

 const int mod=1e9 + ;

 int n, m, match[N];

 bool d[N][N], vis[N];

 bool edge[N][N];

 int path(int u) {

     for(int v = ; v <= n; v++) {

         if(edge[u][v] && !vis[v]) {

             vis[v] = true;

             if(match[v] == - || path(match[v])) {

                 match[v] = u;

                 return ;

             }

         }

     }

     return ;

 }

 int main() {

     memset(match, -, sizeof(match));

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

     for(int i = ; i <= m; i++) {

         int u, v; scanf("%d%d", &u, &v);

         d[u][v] = true;

     }

     for(int k = ; k <= n; k++) {

         for(int i = ; i <= n; i++) {

             for(int j = ; j <= n; j++) {

                 d[i][j] |= d[i][k] && d[k][j];

             }

         }

     }

     for(int i = ; i <= n; i++) {

         for(int j = ; j <= n; j++) {

             if(d[i][j] && i != j) {

                 edge[i][j] = ;

             }

         }

     }

     int ans = n;

     for(int i = ; i <= n; i++) {

         memset(vis, false, sizeof(vis));

         if(path(i)) ans--;

     }

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

     return ;

 }

 /*

 */