学步园

思路：DAC图的最小路径覆盖问题 = 顶点数-最大匹配；

#include <stdio.h>
#include <string.h>
#define M 150

int n,link[M],map[M][M],vis[M];

int DFS (int u)
{
    int v;
    for (v = 1;v
<= n;v ++)
    {
       
if (!vis[v]&&map[u][v])
       
{
           
vis[v] = 1;
           
if (link[v] == -1||DFS(link[v]))
           
{
               
link[v] = u;
               
return 1;
           
}
       
}
    }
    return
0;
}
int MaxMatch()
{
    int u,res =
0;
    memset
(link,-1,sizeof(link));
    for (u = 1;u
<= n;u ++)
    {
       
memset (vis,0,sizeof(vis));
       
if (DFS(u))
           
res ++;
    }
    return
res;
}
int main ()
{
    int
t,m,i,j;
    scanf
("%d",&t);
    while (t
--)
    {
       
scanf ("%d%d",&n,&m);
       
memset (map,0,sizeof(map));

       
while (m --)
       
{
           
scanf ("%d%d",&i,&j);
           
map[i][j] = 1;
       
}
       
int ans = n - MaxMatch();
       
printf ("%d\n",ans);
    }
    return
0;
}