POJ 2771

 1 #include <iostream>
 2 #include <string>
 3 #define MAXN 505
 4 
 5 using namespace std;
 6 
 7 int _m[MAXN][MAXN];
 8 int match[MAXN];
 9 bool ck[MAXN];
10 
11 struct node
12 {
13     int _high;
14     char M_F;
15     string _music;
16     string _habit;
17 };
18 int hungary(int a,int b);
19 node _node[MAXN];
20 
21 int main()
22 {
23    // freopen("acm.acm","r",stdin);
24     int test;
25     int i;
26     int j;
27     int n;
28     cin>>test;
29     while(test --)
30     {
31         cin>>n;
32         for(i = 0; i < n; ++ i)
33         {
34             cin>>_node[i]._high;
35             cin>>_node[i].M_F;
36             cin>>_node[i]._music;
37             cin>>_node[i]._habit;
38         }
39         memset(_m,0,sizeof(_m));
40         for(i = 0; i < n; ++ i)
41         {
42             for(j = 0; j < i; ++ j)
43             {
44                 if(abs(_node[i]._high-_node[j]._high) <= 40 && _node[i].M_F != _node[j].M_F && _node[i]._music == _node[j]._music && _node[i]._habit != _node[j]._habit)
45                 {
46                     _m[i][j] = 1;
47                     _m[j][i] = 1;
48                 }
49             }
50         }
51         cout<<n-hungary(n,n)/2<<endl;
52     }
53 }
54 
55 /////////////////////////////////////////////////////////////////////////
56 //hungary算法，自己写的模板！
57 /////////////////////////////////////////////////////////////////////////
58 bool search(int a,int b,int x)
59 {
60     int i;
61     int t;
62         for ( i = 0 ; i < b ; i++)
63         if (_m[x][i] && ! ck[i])
64         {
65             ck[i] = true;
66             t = match[i];
67             match[i] = x;
68             if (t == -1 || search(a,b,t))
69                 return true;
70             match[i] = t;
71         }
72     return false;
73 }
74 
75 int hungary(int a,int b)
76 {
77     memset(match,-1,sizeof(match));
78     int max_match = 0;
79     int i;
80     for ( i = 0 ; i < a ; i++)
81     {
82         memset(ck,false,sizeof(ck));
83         if (search(a,b,i))
84             max_match++;
85     }
86     return max_match;
87 }