学步园

思路：是求最小点覆盖 = 最大匹配 所以转换成求最大匹配

#include <stdio.h>
#include <string.h>
#define M 505
int map[M][M],xM[M],yM[M],vis[M];
int n;

int dfs (int u)
{
    int v;
    for (v = 1;v
<= n;v ++)
       
if (map[u][v]&&!vis[v])
       
{
           
vis[v] = 1;
           
if (yM[v] == -1||dfs(yM[v]))
           
{
               
yM[v] = u;
               
xM[u] = v;
               
return 1;
           
}
       
}
    return
0;
}
int MaxMatch()
{
    int u,res =
0;
    memset
(xM,-1,sizeof(xM));
    memset
(yM,-1,sizeof(yM));
    for (u = 1;u
<= n;u ++)
       
if (xM[u] == -1)
       
{
           
memset (vis,0,sizeof(vis));
           
if (dfs (u))
               
res ++;
       
}
    return
res;
}
int main ()
{
    int
k,i,j;
    scanf
("%d%d",&n,&k);
    memset
(map,0,sizeof(map));
    while (k
--)
    {
       
scanf ("%d%d",&i,&j);
       
map[i][j] = 1;
    }
    int ans =
MaxMatch ();
    printf
("%d\n",ans);
    return
0;
}