题目链接
解题思路：

• 裸的最小路径覆盖，不过因为时间复杂度，要把普通的二分图匹配改为hk匹配

AC代码：

// Test1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
//DAG的最小路径覆盖数 = DAG图中的节点数 - 相应二分图中的最大匹配数
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 1510;
int T, n, m;
int graph[maxn][maxn << 1], vis[maxn << 1], dis[maxn << 1], match[maxn << 1];
void Init() {memset(match, 0, sizeof(match));cin >> n >> m;int x, y;memset(graph, 0, sizeof(graph));for (int i = 1; i <= m; i++) {cin >> x >> y;graph[x][n + y] = 1;}
}
bool bfs() {memset(dis, 0, sizeof(dis));queue <int> que;for (int i = 1; i <= n; i++)if (!match[i])que.push(i);bool flag = false;while (!que.empty()) {int x = que.front(); que.pop();for (int i = n + 1; i <= 2 * n; i++) {if (!dis[i] && graph[x][i]) {dis[i] = dis[x] + 1;if (!match[i]) flag = true;else dis[match[i]] = dis[i] + 1, que.push(match[i]);}}}return flag;
}
bool dfs(int x) {for (int i = n + 1; i <= 2 * n; i++) {if (vis[i] || dis[i] != dis[x] + 1 || !graph[x][i]) continue; vis[i] = 1;if (!match[i] || dfs(match[i])) {match[x] = i, match[i] = x;return true;}}return false;
}
int hk_match() {int sum = 0;while (bfs()) {memset(vis, 0, sizeof(vis));for (int i = 1; i <= n; i++)if (!match[i] && dfs(i))sum++;}return sum;
}
int main() {cin >> T;while (T--) {Init();int ans = hk_match();cout << n - ans << endl;}return 0;
}