UVAlive3415 Guardian of Decency（最大独立集）

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

【思路】

二分图的最大独立集。

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

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

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

【代码】

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn =  +;

 const int maxl = ;

 bool T[maxn];

 int lky[maxn];

 vector<int> G[maxn];

 bool match(int u) {

     for(int i=;i<G[u].size();i++) {

         int v=G[u][i];

         if(!T[v]) {

             T[v]=;

             if(!lky[v] || match(lky[v])) {

                 lky[v]=u;

                 return true;

             }

         }

     }

     return false;

 }

 int n;

 char sex[maxn][],mus[maxn][maxl],pe[maxn][maxl];

 int h[maxn];

 int main() {

     int k;

     scanf("%d",&k);

     while(k--) {

         scanf("%d",&n);

         for(int i=;i<=n;i++) G[i].clear();

         for(int i=;i<=n;i++) {

             scanf("%d%s%s%s",&h[i],sex[i],mus[i],pe[i]);

                 for(int j=;j<i;j++)

                     if(sex[j][]!=sex[i][] && abs(h[i]-h[j])<= && strcmp(mus[i],mus[j])== && strcmp(pe[i],pe[j])!=)

                         if(sex[i][]=='M') G[i].push_back(j); else G[j].push_back(i);

         }

         memset(lky,,sizeof(lky));

         int ans=;

         for(int i=;i<=n;i++) {

             memset(T,,sizeof(T));

             if(match(i)) ans++;

         }

         printf("%d\n",n-ans);

     }

     return ;

 }