HDU 2119 Matrix

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2119

解题思路：

处理数据，使用公式最小点覆盖数=最大匹配数，使用匈牙利算法求二分图最大匹配即可。

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 int n,m,e[110][110],book[220],cx[110],cy[110];
 4 int Maxmatch();
 5 int path(int u);
 6 int main()
 7 {
 8     int i,j;
 9     while(scanf("%d",&n), n != 0)
10     {
11         scanf("%d",&m);
12         for(i=1;i<=n;i++)
13             for(j=1;j<=m;j++)
14                 scanf("%d",&e[i][j]);
15         printf("%d
",Maxmatch());    
16     } 
17     return 0;
18 } 
19 int Maxmatch()
20 {
21     int i,res=0;
22     memset(cx,0xff,sizeof(cx));
23     memset(cy,0xff,sizeof(cy));
24     for(i=1;i<=n;i++)
25     {
26         if(cx[i] == -1)
27         {
28             memset(book,0,sizeof(book));
29             res += path(i);
30         }
31     }
32     return res;
33 }
34 int path(int u)
35 {
36     int v;
37     for(v=1;v<=m;v++)
38     {
39         if(e[u][v] && !book[v])
40         {
41             book[v]=1;
42             if(cy[v] == -1|| path(cy[v]))
43             {
44                 cx[u]=v;
45                 cy[v]=u;
46                 return 1;
47             }
48         }
49     }
50     return 0;
51 }