UVAlive3415 Guardian of Decency（最大独立集）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34831

【思路】

二分图的最大独立集。

即在二分图中选取最多的点，使点与点之间不相邻。

最大独立集为最小覆盖集的补集。

男者X结点，女者Y结点，连边(Xi,Yj)当且仅当两者4个条件都不满足。

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int maxn =  1000+10;
 9 const int maxl = 101;
10 
11 bool T[maxn];
12 int lky[maxn];
13 vector<int> G[maxn];
14 
15 bool match(int u) {
16     for(int i=0;i<G[u].size();i++) {
17         int v=G[u][i];
18         if(!T[v]) {
19             T[v]=1;
20             if(!lky[v] || match(lky[v])) {
21                 lky[v]=u;
22                 return true;
23             }
24         }
25     }
26     return false;
27 }
28 
29 int n;
30 char sex[maxn][5],mus[maxn][maxl],pe[maxn][maxl];
31 int h[maxn];
32 
33 int main() {
34     int k;
35     scanf("%d",&k);
36     while(k--) {
37         scanf("%d",&n);
38         for(int i=1;i<=n;i++) G[i].clear(); 
39         for(int i=1;i<=n;i++) {
40             scanf("%d%s%s%s",&h[i],sex[i],mus[i],pe[i]);
41                 for(int j=1;j<i;j++)
42                     if(sex[j][0]!=sex[i][0] && abs(h[i]-h[j])<=40 && strcmp(mus[i],mus[j])==0 && strcmp(pe[i],pe[j])!=0) 
43                         if(sex[i][0]=='M') G[i].push_back(j); else G[j].push_back(i);
44         }
45         memset(lky,0,sizeof(lky));
46         int ans=0;
47         for(int i=1;i<=n;i++) {
48             memset(T,0,sizeof(T));
49             if(match(i)) ans++;
50         }
51         printf("%d
",n-ans);
52     }
53     return 0;
54 }