题目链接：bzoj系列往后省略题目链接

题目分类：网络流

题意：

给出一个有向无环图，求他的最长反链。

题解：

根据Dilworth定理，偏序集的最长反链（最大独立集）=最小链覆盖（最小不相交路径覆盖）

所以先对原图进行一次传递闭包，然后拆点连边做最小不相交路径覆盖。

程序：

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int st[3000],ed;
struct node
{
    int next,to,fl,opt;
}g[4000000];
inline void add(int x,int y,int z)
{
//	printf("%d %d %d\n",x,y,z);
	ed++;
	g[ed].to=y;
	g[ed].next=st[x];
	g[ed].fl=z;
	g[ed].opt=ed+1;
	st[x]=ed;
	ed++;
	g[ed].to=x;
	g[ed].next=st[y];
	g[ed].fl=0;
	g[ed].opt=ed-1;
	st[y]=ed;
}
int x1,x2,x3,lev[3000],des;
inline bool makelev()
{
	queue<int>q;
	q.push(0);
	memset(lev,0,sizeof(lev));
	lev[0]=1;
	while (!q.empty())
	{
		x1=q.front();q.pop();
		for (int i=st[x1];i!=0;i=g[i].next)
		{
			if(lev[g[i].to]==0&&g[i].fl!=0)
			{
				q.push(g[i].to);
				lev[g[i].to]=lev[x1]+1;
				if(g[i].to==des)return true;
			}
		}
	}return false;
}	
int stap,sta[3000],spre[3000],stae[3000];
int maxflow;
inline void extend()
{
	int del;
	stap=1;
	sta[1]=0;
	for (int i=0;i<=des;i++)
	{
		spre[i]=st[i];
	}
	while (stap!=0)
	{
		x1=sta[stap];
	//	printf("%d\n",x1);
		if(x1!=des)
		{
            for (;spre[x1]!=0;spre[x1]=g[spre[x1]].next)
            {
                if(g[spre[x1]].fl!=0&&lev[x1]+1==lev[g[spre[x1]].to])
                {
                    break;
                }
            }
            if(spre[x1]!=0)
            {
                stap++;
                stae[stap]=spre[x1];
                sta[stap]=g[spre[x1]].to;
            }
            else
            {
                stap--;lev[x1]=0;
            }
		}
		else
		{
			del=1000000000;
			for (int i=stap;i>=2;i--)
			{
				del=min(del,g[stae[i]].fl);
			}
			maxflow+=del;
			for (int i=stap;i>=2;i--)
			{
				g[stae[i]].fl-=del;
				g[g[stae[i]].opt].fl+=del;
                if(g[stae[i]].fl==0)stap=i-1;
			}
		}
	}
}
inline void dinic()
{
    maxflow=0;
    while (makelev())extend();//,printf("%d\n",maxflow);;
}
int n,m,dp[1200][1200];
int main()
{
	scanf("%d %d",&n,&m);
	des=n+n+1;
	for (int i=1;i<=n;i++)
	{
		add(0,i,1);
		add(i+n,des,1);
	}
	for (int i=1;i<=m;i++)
	{
		scanf("%d %d",&x1,&x2);
		dp[x1][x2]=1;
	}
	for (int k=1;k<=n;k++)
	{
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
			{
				if(dp[i][k]==1&&dp[k][j]==1)dp[i][j]=1;
			}
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if(i!=j&&dp[i][j]==1)
			add(i,j+n,1);
		}
	}
	dinic();
	printf("%d\n",n-maxflow);
    return 0;
}