pku 1043 What's In A Name ?

1. #include <cstdio>
2. #include <cstring>
3. #include <algorithm>
4. using namespace std ;
5. const int MAXN = 21 ;
6. const int Max = 21 ;
7. struct CRIMINAL
8. {
9.     char Name[MAXN] ;
10.     char ID[MAXN] ;
11.     int pos ;
12. }Criminal[MAXN] ;
13. int CnalNum ;
14. bool CnalLeft[MAXN] ;
15. char userID[MAXN][MAXN] ;
16. int leftNum , rightNum , link[MAXN] ;   
17. bool array[Max][Max] , use[MAXN];
18. bool find( int t )
19. {
20.     int i ; 
21.     for ( i = 0 ; i < rightNum ; i++ )
22.     {
23.         if ( !use[i] && array[t][i] )
24.         {
25.             use[i] = true ;
26.             if ( link[i] == -1 || find(link[i]) )
27.             {
28.                 link[i] = t ;
29.                 return true ;
30.             }
31.         }
32.     }
33.     return false ;
34. }
35. int Bihungry()
36. {
37.     int i , ans = 0 ;
38.     memset(link, 0xff, sizeof(link)) ;
39.     for ( i = 0 ; i < leftNum ; i++ )
40.     {
41.         memset(use, 0, sizeof(use)) ;
42.         if ( find( i ) )
43.             ans++ ;
44.     }
45.     return ans ;
46. }
47. int FindPos( char *str )
48. {
49.     int i , pos = -1 ;
50.     for ( i = 0 ; i < CnalNum ; i++ )
51.         if ( strcmp( Criminal[i].Name, str ) == 0 )
52.         {
53.             pos = i ;
54.             break ;
55.         }
56.     return pos ;
57. }
58. int FindIDPos( char *id )
59. {
60.     int i , pos ;
61.     for ( i = 0 ; i < rightNum ; i++ )
62.         if ( strcmp( userID[i], id ) == 0 )
63.         {
64.             pos = i ;
65.             break ;
66.         }
67.     return pos ;
68. }
69. void Init()
70. {
71.     CnalNum = 0 ;
72.     memset(CnalLeft, 1, sizeof(CnalLeft)) ;
73.     memset(array, 1, sizeof(array)) ;
74.     int i ;
75.     for ( i = 0 ; i < MAXN ; i++ )
76.     {
77.         strcpy(Criminal[i].ID, "???") ;
78.     }
79. }
80. int cmp( const void* fc, const void *sc )
81. {
82.     return ( strcmp((*(CRIMINAL*)fc).Name,(*(CRIMINAL*)sc).Name) ) ;
83. }
84. int main()
85. {
86.     int n , i , j , pos ;
87.     char cmd[2] , name[MAXN] ;
88.     scanf("%d", &n) ;
89.     rightNum = n ;
90.     Init() ;
91.     for ( i = 0 ; i < n ; i++ )
92.     {
93.         scanf("%s", &userID[i]) ;
94.     }
95.     while ( true )
96.     {
97.         scanf("%s", &cmd) ;
98.         if ( strcmp( cmd , "Q" ) == 0 ) break ;
99.         scanf("%s", &name) ;
100.         if ( strcmp( cmd , "E" ) == 0 )
101.         {
102.             pos = FindPos( name ) ;
103.             if ( pos == -1 )
104.             {
105.                 strcpy( Criminal[CnalNum].Name, name ) ;
106.                 pos = CnalNum ;
107.                 CnalNum++ ;
108.             }
109.             CnalLeft[pos] = false ;
110.         }
111.         else if ( strcmp( cmd , "L" ) == 0 )
112.         {
113.             pos = FindPos( name ) ;
114.             CnalLeft[pos] = true ;
115.         }
116.         else if ( strcmp( cmd, "M" ) == 0 )
117.         {
118.             pos = FindIDPos( name ) ;
119.             for ( i = 0 ; i < n ; i++ )
120.             {
121.                 if ( CnalLeft[i] )
122.                 {
123.                     array[i][pos] = false ;
124.                 }
125.             }
126.         }
127.     }
128.     leftNum = CnalNum ;
129.     for ( i = 0 ; i < leftNum ; i++ )
130.     {
131.         for ( j = 0 ; j < rightNum && strcmp(Criminal[i].ID, "???") == 0 ; j++ )
132.         {
133.             if ( array[i][j] )
134.             {
135.                 array[i][j] = false ;
136.                 if ( Bihungry() < leftNum )
137.                     strcpy(Criminal[i].ID, userID[j]) ;
138.                 array[i][j] = true ;
139.             }
140.         }
141.     }
142.     qsort( Criminal, CnalNum, sizeof(Criminal[0]), cmp) ;
143.     for ( i = 0 ; i < leftNum ; i++ )
144.     {
145.         printf("%s:%s/n", Criminal[i].Name, Criminal[i].ID) ;
146.     }
147.     return 0 ;
148. }