POJ 2771 Guardian of Decency

题意：

一个老师想带几个同学出去，但是他怕他们会谈恋爱，所以带出去的同学两两之间必须满足如下条件之一：

①身高差大于40 ②同性 ③喜欢的音乐风格不同 ④喜欢的运动相同

思路：

每两个人之间进行判断，如果不满足上面4个之一，则连一条线，说明他们是不能同时带出去的。然后找一个最大匹配，说明这几对中每队只能带出去一人，这样答案就很明显了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 const int maxn=500+5;
 8 
 9 int n;
10 
11 struct node
12 {
13     int height;
14     char sex;
15     char music[105];
16     char sport[105];
17 }a[maxn];
18 
19 int g[maxn][maxn];
20 int vis[maxn];
21 int match[maxn];
22 
23 bool judge(int i,int j)
24 {
25     if(abs(a[i].height-a[j].height)>40 || a[i].sex == a[j].sex || strcmp(a[i].music,a[j].music)||!strcmp(a[i].sport,a[j].sport)) return true;
26     return false;
27 }
28 
29 bool dfs(int x)
30 {
31     for(int i=0;i<n;i++)
32     {
33         if(!vis[i] && g[x][i])
34         {
35             vis[i]=1;
36             if(match[i]==-1 || dfs(match[i]))
37             {
38                 match[i]=x;
39                 return true;
40             }
41         }
42     }
43     return false;
44 }
45 
46 int main()
47 {
48     //freopen("D:\txt.txt","r",stdin);
49     int T;
50     scanf("%d",&T);
51     while(T--)
52     {
53         memset(g,0,sizeof(g));
54         scanf("%d",&n);
55         for(int i=0;i<n;i++)
56         {
57             cin>>a[i].height>>a[i].sex>>a[i].music>>a[i].sport;
58         }
59         for(int i=0;i<n;i++)
60             for(int j=0;j<n;j++)
61         {
62 
63             if(i==j)  continue;
64             if(!judge(i,j))  g[i][j]=1;
65         }
66         int ans=0;
67         memset(match,-1,sizeof(match));
68         for(int i=0;i<n;i++)
69         {
70             memset(vis,0,sizeof(vis));
71             {
72                 if(dfs(i)) ans++;
73             }
74         }
75         cout<<n-ans/2<<endl;
76     }
77 }