题目链接：

题意：

有一些同学，要从中选出一些同学来，人数尽量多，但是，两两之间要满足至少一个条件（身高差>40，性别相同，。。。）

分析：

最大独立集：尽量选择多的结点，任意两个结点不相邻；

男同学X，女同学Y，如果可能产生关系，连一条边，这样这两个人就不会在一起；

 

最大独立集=n-最大匹配

证明：

最小点覆盖 = 对于每一条边，至少有一个点要被选中

最大独立集 = 对于每一条边，最多一个点被选中

从定义中可以看出，这两个是互补的；

1 #include 
      
        2  3 using namespace std; 4  5 const int maxn = 500+5; 6  7 struct BPM { 8     int n,m; 9     vector
       
         G[maxn];10     int left[maxn];11     bool T[maxn];12 13     int right[maxn];14     bool S[maxn];15 16     void init(int n,int m) {17         this->n = n;18         this->m = m;19         for(int i=0;i
        
         >t;72     while(t--) {73         int n;74         cin>>n;75         vector
         
           male,female;76         for(int i=0;i
          
           >h>>gender>>music>>sport;80             if(gender[0]=='M') male.push_back(Student(h,music,sport));81             else female.push_back(Student(h,music,sport));82         }83         int x = male.size();84         int y = female.size();85         sol.init(x,y);86         for(int i=0;i