【题意】求DAG上最多的点使得互不可达。

【算法】floyd+最大匹配

【题解】

链是DAG上的一个点集，集合内的点相互单向可达。

反链是DAG上的一个点集，集合内的点相互不可达。

题目显然是求最长反链，转化为最小链覆盖。

最小链覆盖只要求可达，最小路径覆盖却要求相连。

所以floyd传递闭包（用floyd解决01可达信息称为传递闭包），然后最小路径覆盖ans=n-最大匹配。

二分图记得开双倍点。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=210,inf=0x3f3f3f3f;bool map[maxn][maxn];int tot=1,n,m,first[maxn],S,T,d[maxn],cur[maxn];//最小路径覆盖要开两倍点! struct edge{
    int v,flow,from;}e[maxn*maxn*3];void floyd(){    for(int k=1;k<=n;k++)        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)                map[i][j]=map[i][j]||(map[i][k]&map[k][j]);}void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].flow=w;e[tot].from=first[u];first[u]=tot; tot++;e[tot].v=u;e[tot].flow=0;e[tot].from=first[v];first[v]=tot;}queue
          
           q;bool bfs(){    q.push(S);    memset(d,-1,sizeof(d));    d[S]=0;    while(!q.empty()){        int x=q.front();q.pop();        for(int i=first[x];i;i=e[i].from)        if(e[i].flow&&d[e[i].v]==-1){            d[e[i].v]=d[x]+1;            q.push(e[i].v);        }    }    return d[T]!=-1;}int dinic(int x,int a){    if(x==T||a==0)return a;    int f,flow=0;    for(int& i=cur[x];i;i=e[i].from)    if(d[e[i].v]==d[x]+1&&e[i].flow&&(f=dinic(e[i].v,min(a,e[i].flow)))>0){        e[i].flow-=f;        e[i^1].flow+=f;        flow+=f;        a-=f;        if(a==0)break;//...    }    return flow;}    int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++){        int u,v;        scanf("%d%d",&u,&v);        map[u][v]=1;    }    for(int i=1;i<=n;i++)map[i][i]=0;    floyd();    S=0;T=2*n+1;    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            if(map[i][j])insert(i,j+n,1);    for(int i=1;i<=n;i++){insert(S,i,1);insert(i+n,T,1);}    int ans=n;    while(bfs()){        for(int i=S;i<=T;i++)cur[i]=first[i];        ans-=dinic(S,inf);    }    printf("%d",ans);    return 0;}