题意：
思路：Dilworth定理：对于一个偏序集，最少链划分等于最长反链长度。 Dilworth定理的对偶定理：对于一个偏序集，其最少反链划分数等于其最长链的长度。
最长反链=最小路径覆盖
floyd传递闭包后，用n-二分图最大匹配数即为答案（因为是点可重最小路径覆盖，所以要先用floyd求传递闭包）
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef int lint; const int inf= 0x3f3f3f3f; const int maxn = 505; struct dinic{ static const int N = 1005; static const int M = 2000005; static const lint inf = 0x3f3f3f3f; int he[N],ne[M],ver[M],d[N]; lint edge[M]; int s,t,tot; queue<int> que; void init( int n ){ for( int i = 0;i <= n;i++ ){ he[i] = 0; } tot = 1; } void add( int x,int y,lint z ){ ver[++tot] = y; ne[ tot ] = he[x]; he[x] = tot; edge[ tot ] = z; ver[++tot] = x; ne[tot] = he[y]; he[y] = tot;edge[tot] = 0; } bool bfs(){ memset( d,0,sizeof( d ) ); while( que.size() ) que.pop(); que.push( s ); d[s] = 1; while( que.size() ){ int x = que.front(); que.pop(); for( int cure = he[x];cure;cure = ne[cure] ){ int y = ver[cure]; if( edge[cure] && !d[y] ){ que.push( y ); d[ y ] = d[x] + 1; if( y == t ) return 1; } } } return 0; } lint dfs( int x,lint flow ){ if( x== t ) return flow; lint rest = flow,k; for( int cure = he[x];cure && rest;cure = ne[cure] ){ int y = ver[cure]; if( edge[cure] && d[ y ] == d[x] + 1 ){ k = dfs( y,min( rest,edge[cure] ) ); if( !k ) d[ y ] = 0; edge[cure] -= k; edge[ cure^1 ] += k; rest -= k; } } return flow - rest; } lint max_flow( int x,int y ){ s = x; t = y; lint maxflow = 0; lint flow = 0; while( bfs() ) while( flow = dfs( s,inf ) ) maxflow += flow; return maxflow; } } g; int dist[maxn][maxn]; void floyd(int n){ for( int k = 1;k <= n;k++ ){ for( int i = 1;i<= n;i++ ){ for( int j = 1;j <= n;j++ ){ if( dist[i][j] > dist[i][k]+dist[k][j] ){ dist[i][j] = dist[i][k]+dist[k][j]; } } } } } int main(){ int n,m,S,T; scanf("%d%d",&n,&m); S = 0,T = 2*n+1; g.init(T); for( int i = 1;i<= n;i++ ){ for( int j = 1;j <= n;j++ ){ dist[i][j] = inf; } dist[i][i] = 0; } for( int x,y,i = 1;i <= m;i++ ){ scanf("%d%d",&x,&y); dist[x][y] = 1; } floyd(n); for( int i = 1;i <= n;i++ ){ g.add(S,i,1); g.add(i+n,T,1); } for( int i = 1;i <= n;i++ ){ for( int j = 1;j <= n;j++ ){ if( i == j || dist[i][j] == inf ) continue; g.add( i,j+n,1 ); } } int ans = n - g.max_flow(S,T); printf("%d\n",ans); return 0; }
