1 /* 2 匈牙利算法模版题 3 邻接表实现，邻接矩阵超时 4 最大匹配问题 5  */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 using namespace std;10 const int maxn = 505;11 vector
        
          v[maxn];//x = v[i][j]表示i可以与x进行匹配12 int vis[maxn],match[maxn];//vis[i]表示i已经访问（匹配）过为了防止在每次dfs中重复访问某点,x = match[i]表示x现在和i匹配13 bool dfs(int x)14 {15     for(int i = 0; i < v[x].size(); ++i)16     {17         int t = v[x][i];18         if(!vis[t])19         {20             vis[t] = 1;21             if(match[t] == -1 || dfs(match[t]))22             {match[t] = x; return true;}23         }24     }25     return false;26 }27 int hungary(int n)28 {29     int ans = 0;30     for(int i = 1; i <= n; ++i)31     {32         memset(vis,0,sizeof vis);33         if(dfs(i)) ++ans;34     }35     return ans;36 }37 int main()38 {39     int t,n,m,x,y;40     scanf("%d",&t);41     while(t--)42     {43         scanf("%d%d",&n,&m);44         for(int i = 1; i <= n; ++i)45             v[i].clear();46         memset(match, -1, sizeof match);47         while(m--)48         {49             scanf("%d%d",&x,&y);50             v[x].push_back(y);51         }52         printf("%d\n",hungary(n));53     }54     return 0;55 }