\(\text{Problem}\)
求一个 \(DAG\) 的最长反链
\(\text{Solution}\)
由 \(Dilworth\) 定理只最长反链等于最小链覆盖
而原图的链是可相交的，所以我们先做一遍 \(Floyd\) 传递闭包，使得原图的链不必相交即可覆盖
这样就转化为最小链覆盖（顶点不可相交）
于是用网络流经典模型解决
\(\text{Code}\)
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 405;
int n, m, h[N], S, T, g[N][N];
struct edge{
int to, nxt, w;
}e[100005];
inline void add(int u, int v, int w)
{
static int tot = 1;
e[++tot] = edge{v, h[u], w}, h[u] = tot;
}
int Q[N], cur[N], dep[N];
inline int bfs()
{
for(int i = S; i <= T; i++) cur[i] = h[i], dep[i] = 0;
int head = 0, tail = 1;
Q[1] = S, dep[S] = 1;
while (head < tail)
{
int now = Q[++head];
for(int i = h[now]; i; i = e[i].nxt)
{
int v = e[i].to;
if (dep[v] || !e[i].w) continue;
dep[v] = dep[now] + 1, Q[++tail] = v;
}
}
return dep[T];
}
int dfs(int x, int mi)
{
if (x == T || mi <= 0) return mi;
int flow = 0;
for(int i = cur[x]; i; i = e[i].nxt)
{
cur[x] = i;
int v = e[i].to;
if (dep[v] ^ (dep[x] + 1) || !e[i].w) continue;
int f = dfs(v, min(mi, e[i].w));
if (f <= 0) continue;
flow += f, mi -= f, e[i].w -= f, e[i ^ 1].w += f;
if (mi <= 0) break;
}
return flow;
}
int dinic()
{
int res = 0;
while (bfs()) res += dfs(S, N);
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1, x, y; i <= m; i++) scanf("%d%d", &x, &y), g[x][y] = 1;
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
if (g[i][k])
for(int j = 1; j <= n; j++)
if (g[k][j]) g[i][j] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if (g[i][j]) add(i, j + n, 1), add(j + n, i, 0);
T = 2 * n + 1;
for(int i = 1; i <= n; i++) add(S, i, 1), add(i, S, 0), add(i + n, T, 1), add(T, i + n, 0);
printf("%d\n", n - dinic());
}