DAG的最小路径覆盖，模板题
题目意思：
有n个点，m条边的有向无环图，每个点放一名士兵，然后士兵沿着图走，直到不能走
为止， 每条只能由一名士兵走过，问最少需要多少士兵。
本题要点：
1、图很小，可以用邻接矩阵来存图。
2、有向无环图，写成对应的二分图：
当点x -> y, 看成左部节点x 指向右部节点 y + n, 左部节点的范围 1 ~ n, 右部节点范围 n + 1 ~ 2 * n
3、 最小路径覆盖 = 点数 - 二分图最大匹配。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 300;
int a[MaxN][MaxN], match[MaxN];
bool vis[MaxN];
int T, n, m;bool dfs(int x)
{
for(int y = n + 1; y <= 2 * n; ++y){
if(!a[x][y] || vis[y])continue;vis[y] = true;if(!match[y] || dfs(match[y])){
match[y] = x;return true;}}return false;
}int main()
{
int x, y;scanf("%d", &T);while(T--){
memset(a, 0, sizeof a);memset(match, 0, sizeof match);scanf("%d%d", &n, &m); for(int i = 0; i < m; ++i){
scanf("%d%d", &x, &y);a[x][y + n] = 1;}int ans = 0;for(int i = 1; i <= n; ++i){
memset(vis, false, sizeof vis); if(dfs(i))++ans;}printf("%d\n", n - ans);}return 0;
}/* 2 4 3 3 4 1 3 2 3 3 3 1 3 1 2 2 3 *//* 2 1 */