poj 1258 -- Asteroids

 1 /*======================================================================
 2  *           Author :   kevin
 3  *         Filename :   Asteroids.cpp
 4  *       Creat time :   2014-07-13 08:51
 5  *      Description :
 6  ========================================================================*/
 7 #include <iostream>
 8 #include <algorithm>
 9 #include <cstdio>
10 #include <cstring>
11 #include <queue>
12 #include <cmath>
13 #define clr(a,b) memset(a,b,sizeof(a))
14 #define M 550
15 
16 using namespace std;
17 
18 int g[M][M];
19 int n,k,used[M],linker[M];
20 bool DFS(int u)
21 {
22     for(int v = 0; v < n; v++){
23         if(g[u][v] && !used[v]){
24             used[v] = 1;
25             if(linker[v] == -1 || DFS(linker[v])){
26                 linker[v] = u;
27                 return true;
28             }
29         }
30     }
31     return false;
32 }
33 int MaxMatch()
34 {
35     int res = 0;
36     clr(linker,-1);
37     for(int u = 0; u < n; u++){
38         clr(used,0);
39         if(DFS(u)) res++;
40     }
41     return res;
42 }
43 int main(int argc,char *argv[])
44 {
45     while(scanf("%d%d",&n,&k)!=EOF){
46         int a,b;
47         clr(g,0);
48         for(int i = 0; i < k; i++){
49             scanf("%d%d",&a,&b);
50             g[a-1][b-1] = 1;
51         }
52         int ans = MaxMatch();
53         printf("%d\n",ans);
54     }
55     return 0;
56 }