poj 3041 二分图最小点集覆盖

定理：二分图的最大匹配=最小点覆盖。

思路：将所有行看做点集X，所有列看做点集Y，如果在[i, j]处有小行星，则建立一条从i到j的边，然后求最大匹配即为最小点覆盖数即为答案。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 501;
 7 const int M = N * N;
 8 int head[N];
 9 int mark[N];
10 bool visit[N];
11 int n, m, e;
12 
13 void init()
14 {
15     e = 0;
16     memset( head, -1, sizeof(head) );
17 }
18 
19 struct Edge
20 {
21     int v, next;
22 } edge[M];
23 
24 void addEdge( int u, int v )
25 {
26     edge[e].v = v;
27     edge[e].next = head[u];
28     head[u] = e++;
29 }
30 
31 int dfs( int u )
32 {
33     for ( int i = head[u]; i != -1; i = edge[i].next )
34     {
35         int v = edge[i].v;
36         if ( !visit[v] )
37         {
38             visit[v] = 1;
39             if ( mark[v] == -1 || dfs( mark[v] ) )
40             {
41                 mark[v] = u;
42                 return 1;
43             }
44         }
45     }
46     return 0;
47 }
48 
49 int hungary()
50 {
51     memset( mark, -1, sizeof(mark) );
52     int res = 0;
53     for ( int i = 1; i <= n; i++ )
54     {
55         memset( visit, 0, sizeof(visit) );
56         res += dfs(i);
57     }
58     return res;
59 }
60 
61 int main ()
62 {
63     while ( scanf("%d%d", &n, &m) != EOF )
64     {
65         init();
66         while ( m-- )
67         {
68             int u, v;
69             scanf("%d%d", &u, &v);
70             addEdge( u, v );
71         }
72         int ans = hungary();
73         printf("%d
", ans);
74     }
75     return 0;
76 }