题解：P10938

__mt19937__ · 2025-08-13 15:13:30 · 题解

题目大意

给你一个 DAG，让你求出一个最大的 k，使得在图中可以选出 k 个点，这些点互相都不能到达。

解题思路

看到 n \le 200 的数据范围就可以尝试用随机化，每次打乱数组顺序，能加入集合就加入集合里面，这样就可以用很简单的方法 AC 了（其实就是我不会最长反链）。

Code

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define dwn(i,j,k) for(int i=(j);i>=(k);--i)
using namespace std;
const int N=201;
mt19937 rnd(13365312749183220);
int n,m,d[N][N],a[N];
int g(){
    int f[N];
    int s=0;
    rep(i,1,n){
        bool ca=1;
        rep(j,1,s)if(d[a[f[j]]][a[i]]||d[a[i]][a[f[j]]]){ca=0;break;}
        if(ca)f[++s]=i;
    }
    return s;
}
int f(){
    int ms=0;
    rep(i,1,5000){
        shuffle(a+1,a+n+1,rnd);
        int cs=g();
        if(cs>ms)ms=cs;
    }
    return ms;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    rep(i,1,m){
        int u,v;
        cin>>u>>v;
        d[u][v]=1;
    }
    rep(k,1,n)rep(i,1,n)rep(j,1,n)d[i][j]|=d[i][k]&&d[k][j];
    rep(i,1,n)a[i]=i;
    cout<<f();
    return 0;
}