BZOJ1143 [CTSC2008] 祭祀 river

题目大意

给你一个有向图，让你选择最多的点，使得这些点互相不可达。

发现需要一些蛇皮知识点……

直到看到dalao随机化艹过这道题的题解。

必须上啊！！！

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,inx,iny,c[110],ans,cnt;
bool mp[110][110],use[110];
void floyd()
{
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(mp[i][k]&&mp[k][j]) mp[i][j]=true;
}
int main()
{
    srand(1026);
    scanf("%d%d",&n,&m);
    while(m--) scanf("%d%d",&inx,&iny),mp[inx][iny]=true;
    floyd();
    for(int i=1;i<=n;++i) c[i]=i;
    for(int randt=0;randt<=5000;++randt)
    {
        cnt=0;
        memset(use,false,sizeof use);
        random_shuffle(c+1,c+n+1);
        for(int i=1;i<=n;++i)
            if(!use[c[i]])
            {
                cnt++;
                use[c[i]]=true;
                for(int j=1;j<=n;++j) if(mp[c[i]][j]||mp[j][c[i]]) use[j]=true;
            }
        ans=max(ans,cnt);
    }
    printf("%d\n",ans);
}