BZOJ 1143: [CTSC2008]祭祀river（最大独立集）

题面：

　　https://www.lydsy.com/JudgeOnline/problem.php?id=1143

　　一句话题意：给一个DAG（有向无环图），求选出尽量多的点使这些点两两不可达，输出点个数。

　　N、M，分别表示点数和有向边数，n<=100,m<=1000。

题解：

　　第一眼看到题，发现是个DAG之后直接想到了dp，然后发现不可做。

　　然后仔细分析题目，发现就是在所有联通的点对（a，b）中两点不都被选中。

　　欸这不就是个最大独立集吗，

　　于是先floyd判连通性后跑hungary水过。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=,maxm=;

int g[maxn][maxn],fa[maxn],vis[maxn],ans,n,m,head[maxn],cnt;

struct ed{

    int next,to;

}e[maxm];

void add(int u,int v){

    e[++cnt]=(ed){head[u],v};head[u]=cnt;

}

bool hungary(int x){

    for(int i=head[x];i;i=e[i].next){

        int tt=e[i].to;

        if(vis[tt]) continue;

        vis[tt]=;

        if(!fa[tt]||hungary(fa[tt])){

            fa[tt]=x;

            return ;

        }

    }

}

int main(){

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

    int u,v;

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

        scanf("%d%d",&u,&v),g[u][v]=;

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

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

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

                g[i][j]=g[i][j]|(g[i][k]&g[k][j]);

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

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

            if(i!=j&&g[i][j])

                add(i,j);

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

        memset(vis,,sizeof(vis));

        if(hungary(i))

            ans++;

    }

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

    return ;

}