前面的话

这道题显然就是最长反链

根据 \(Dilworth\) 定理：最小链覆盖数 = 最长反链长度

然后传递闭包跑匹配即可

\(luogu\)交了一下，\(WA\) 了

\(QAQ\)

本来各种 \(OJ\) 上都是只要求最长反链，不需要构造方案

虽然原题要构造

然后 \(luogu\) 上的同志写了个 \(SPJ\)， 然后 \(luogu\) 就要输出方案了

切不掉很难受

Sol

先放两个博客:

首先建图后发现最大独立集和最小点覆盖互为补集

而这个图中的最大独立集就是最长反链可能，猜的...(因为两两不可到达)

然后只要知道怎么构造最小点覆盖就好了

第一步

对于一个二分图，这样来做：

先最大匹配

每次从左边找到一个未匹配点增广(假的增广，显然增广不了，因为已经是最大匹配)

然后标记点

最后左边没有标记过的点和右边标记过的点就是最小点覆盖

伪证：因为一条假的增广路一定是左边的点作为开头和结尾的，所以选右边的就能覆盖这个假的增广路

去掉这些点就是要找的最长反链

第二步

找到所有可以出现在最长反链上的点

枚举每个点，删掉它以及可以到达它和它可以到达的点(邻居)

再求最长反链，如果大小减小了 \(1\)，这个点就是可以的(显然选这个点不会和当前的集合冲突)

代码

# include 
    
     # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL int Input(){    RG char c = getchar(); RG int x = 0, z = 1;    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}const int maxn(205);const int maxm(1005);int n, m, ans, match[maxn], to[maxn], vis[maxn], idx, f[maxn][maxn], g[maxn][maxn];int ban[maxn], s[maxn], t[maxn];IL int Dfs(RG int u){    if(ban[u]) return 0;    for(RG int i = 1; i <= n; ++i)        if(f[u][i] && vis[i] != idx && !ban[i]){            vis[i] = idx;            if(!match[i] || Dfs(match[i])){                to[u] = i, match[i] = u;                return 1;            }        }    return 0;}IL void Calc(RG int u){    if(s[u]) return;    s[u] = 1;    for(RG int i = 1; i <= n; ++i)        if(f[u][i] && !t[i]) t[i] = 1, Calc(match[i]);}int main(RG int argc, RG char* argv[]){    n = Input(), m = Input();    for(RG int i = 1; i <= m; ++i) g[Input()][Input()] = 1;    for(RG int i = 1; i <= n; ++i)        for(RG int j = 1; j <= n; ++j)            for(RG int k = 1; k <= n; ++k) g[j][k] |= g[j][i] & g[i][k];    memcpy(f, g, sizeof(f)), ans = n;    for(RG int i = 1; i <= n; ++i) ++idx, ans -= Dfs(i);    printf("%d\n", ans);    for(RG int i = 1; i <= n; ++i) if(!to[i]) Calc(i);    for(RG int i = 1; i <= n; ++i) printf("%d", s[i] && !t[i]);    puts("");    for(RG int nw = 1; nw <= n; ++nw){        for(RG int i = 1; i <= n; ++i) match[i] = to[i] = 0;        RG int ret = 0, nn = 0;        Fill(f, 0), Fill(ban, 0);        for(RG int i = 1; i <= n; ++i)            if(g[i][nw] || g[nw][i] || i == nw) ban[i] = 1;            else ++nn;        ret = nn;        for(RG int i = 1; i <= n; ++i)            for(RG int j = 1; j <= n; ++j)                if(!ban[i] && !ban[j]) f[i][j] = g[i][j];        for(RG int i = 1; i <= n; ++i) if(!ban[i]) ++idx, ret -= Dfs(i);        printf("%d", ret == ans - 1);    }    return 0;}