一开始我以为是最小支配集，后来胡乱YY一下，以为最小支配集 == 最大独立数 == N-最大匹配，结果给我胡乱AC了。后来去网上搜搜解题报告才知道是最小路径覆盖。

CODE：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib> 

using 

namespace std;

#define MAXN 130

#define MAXM 20010

int G[MAXN][MAXN];

int xlink[MAXN];

int ylink[MAXN];

bool vis[MAXN];  

int nx, ny, m;

inline 

void init()

{

    memset(G, 

0, 

sizeof(G));

    memset(xlink, -

1, 

sizeof(xlink));

    memset(ylink, -

1, 

sizeof(ylink));

}

bool ED(

int u)

{

    

for(

int v = 

1; v <= ny; v++) 

if(G[u][v]) 

    {

        

if(!vis[v]) 

        {

            vis[v] = 

1;

            

if(ylink[v] == -

1 || ED(ylink[v])) 

            { 

                xlink[u] = v;

                ylink[v] = u; 

                

return 

true;

            } 

        }

    }

    

return 

false;

}

void MaxMatch()

{

    

int ans = 

0;

    

for(

int i = 

1; i <= nx; i++)

    {

        

if(xlink[i] == -

1)

        {

            memset(vis, 

0, 

sizeof(vis));

            ans += ED(i);

        }

    }

    printf(

"

%d\n

", nx-ans);

}

int main()

{

    

int T;

    scanf(

"

%d

", &T);

    

while(T--)

    {

        init();

        scanf(

"

%d%d

", &nx, &m);

        ny = nx;

        

while(m--)

        {

            

int u, v;

            scanf(

"

%d%d

", &u, &v);

            G[u][v] = 

1;

        }

        MaxMatch();

    }

    

return 

0;

}