题目链接：The Maximum Unreachable Node Set

题目大意：

给定一个偏序集，求最长反链大小。

反链的定义是：链上的任意两点互不可达。

趁机补一补图论的东西。

这道题是道板子题，不过没学过基本上写不出来吧。

首先有两个前置技能：

1.求偏序集上最小不相交链覆盖数

每个点拆成两个点$i$和$i+n$，$x,y$之间有边，就$x$向$y+n$连边。

然后求最大匹配数，答案就是点数-匹配数。

为啥是这样呢？

一开始每个点都是独立路径，每次有一个匹配，就相当于以$x$结尾的路径和$y$开头的路径合并在了一起。

显然$x$不能向多个路径头连边，刚好$1$对$1$匹配。

2.求偏序集上最小可相交链覆盖数

先把原图改成原图的传递闭包，然后再求不相交链覆盖数。

为啥是这样呢？

求出传递封包之后任意两点的可到达性都直接用边连起来了，那么一条边的存在可能是它跨过很多条边后的结果，所以直接不相交覆盖就行了。

3.求偏序集上最大反链

根据Dilworth定理。

偏序集上最大链的长度等于最少反链覆盖数，最大反链等于最小可相交路径覆盖数。

只要求最小可相交路径覆盖数就行了。

不会写匈牙利算法，只会写dinic。

 1 #include <bits/stdc++.h>
 2 #define Mid ((l + r) / 2)
 3 #define lson (rt << 1)
 4 #define rson (rt << 1 | 1)
 5 using namespace std;
 6 int read() {
 7     char c; int num, f = 1;
 8     while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
 9     while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
10     return f * num;
11 }
12 const int N = 2e5 + 1009;
13 const int inf = 0x3f3f3f3f;
14 int n, m, g[109][109], s, t, d[N];
15 int head[N], nxt[N], ver[N], edge[N], tot = 1;
16 queue<int> q;
17 void add(int x, int y, int w) {
18     nxt[++tot] = head[x]; head[x] = tot; ver[tot] = y; edge[tot] = w;
19 }
20 int bfs() {
21     while(q.size()) q.pop(); q.push(s);
22     for(int i = 1; i <= 2 * n + 2; i++) d[i] = 0; d[s] = 1;
23     while(q.size()) {
24         int x = q.front(); q.pop();
25         for(int i = head[x]; i; i = nxt[i]) {
26             if(d[ver[i]] || edge[i] <= 0) continue;
27             d[ver[i]] = d[x] + 1;
28             q.push(ver[i]);
29         }
30     }
31     return d[t] != 0;
32 }
33 int dfs(int x, int flow) {
34     if(x == t) return flow;
35     int res = flow, k;
36     for(int i = head[x]; i && res; i = nxt[i]) {
37         if(d[ver[i]] != d[x] + 1 || edge[i] <= 0) continue;
38         k = dfs(ver[i], min(edge[i], res));
39         if(k == 0) d[ver[i]] = 0;
40         edge[i] -= k;
41         edge[i ^ 1] += k;
42         res -= k;
43     }
44     return flow - res;
45 }
46 int dinic() {
47     int maxflow = 0;
48     while(bfs()) 
49         maxflow += dfs(s, inf);
50     return maxflow;
51 }
52 void work() {
53     n = read(); m = read(); s = n * 2 + 1; t = n * 2 + 2;
54     for(int i = 1; i <= 2 * n + 2; i++) head[i] = 0; tot = 1;
55     for(int i = 1; i <= n; i++) 
56         for(int j = 1; j <= n; j++)
57             g[i][j] = (i == j);
58     for(int i = 1; i <= m; i++) {
59         int x = read(), y = read();
60         g[x][y] = 1;
61     }
62     for(int k = 1; k <= n; k++) 
63         for(int i = 1; i <= n; i++) 
64             for(int j = 1; j <= n; j++) 
65                 g[i][j] |= g[i][k] & g[k][j];
66     for(int i = 1; i <= n; i++) {
67         for(int j = 1; j <= n; j++) if(i != j && g[i][j]) {
68             add(i, j + n, 1);
69             add(j + n, i, 0);
70         }
71         add(s, i, 1);
72         add(i, s, 0);
73         add(i + n, t, 1);
74         add(t, i + n, 0);
75     }
76     printf("%d\n", n - dinic());
77 }
78 signed main()
79 {
80     int Case = read();
81     while(Case--) work();
82     return 0;
83 }