题意：DAG求最小路径覆盖。
注意：二分匹配只试用于求DAG的最小路径覆盖， 有环就不行，具体可以理解证明。
对n个点进行拆点，分成左右两排点，对于边<u, v> 建 <u', v''> 。
然后 最小路径覆盖 == 总点数n - 最大匹配。
简单的证明： 每匹配一对<u，v>就说明u和v在同一条路径上，拿路径数就少1。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 130;
vector <int> edge[maxn];
int n, m;
int pre[maxn];
bool vis[maxn];
bool dfs(int u) {
for(int i = 0; i < (int) edge[u].size(); i++) {
int v = edge[u][i];
if(vis[v]) continue;
vis[v] = 1;
if(pre[v] == -1 || dfs(pre[v])) {
pre[v] = u;
return 1;
}
}
return 0;
}
int main() {
int i, cas;
scanf("%d", &cas);
while(cas--) {
scanf("%d%d", &n, &m);
int x, y;
for(i = 1; i <= n; i++)
edge[i].clear();
while(m--) {
scanf("%d%d", &x, &y);
edge[x].push_back(y);
}
memset(pre, -1, sizeof(pre));
int cnt = 0;
for(i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
cnt += dfs(i);
}
printf("%d
", n-cnt);
}
return 0;
}