Asteroids（匈牙利算法）

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int M = 510 ;
 4 bool map[M][M] ;
 5 int girl[M] ;
 6 bool sta[M] ;
 7 int n , m;
 8 
 9 bool hungary (int x)
10 {
11     for (int i = 1 ; i <= n ; i++) {
12         if (map[x][i] && sta[i] == false) {
13             sta[i] = true ;
14             if (girl[i] == 0 || hungary (girl[i])) {
15                 girl[i] = x ;
16                 return true ;
17             }
18         }
19     }
20     return false ;
21 }
22 
23 int main ()
24 {
25    // freopen ("a.txt" , "r" , stdin) ;
26     while (~ scanf ("%d%d" , &n , &m)) {
27         int x , y , k = 0 ;
28         memset (map , 0 , sizeof(map)) ;
29         memset (girl , 0 , sizeof(girl)) ;
30         for (int i = 0 ; i < m ; i++) {
31             scanf ("%d%d" , &x , &y) ;
32             map[x][y] = 1 ;
33         }
34         int all = 0 ;
35         for (int i = 1 ; i <= n ; i++) {
36             memset (sta , 0 , sizeof(sta)) ;
37             if (hungary (i))
38                 all++ ;
39         }
40         printf ("%d\n" , all) ;
41     }
42     return 0 ;
43 }