poj 3692 二分图最大匹配 - c++编程基础

poj 3692 二分图最大匹配
题意：
已知班级有g个女孩和b个男孩，所有女生之间都相互认识，所有男生之间也相互认识，给出m对关系表示哪个女孩与哪个男孩认识。现在要选择一些学生来组成一个团，使得里面所有人都互相认识，求此团最大人数。

限制：
1 <= g,b <= 200; 0 <= m <= b*g

思路：
求最大团。
最大独立集=|V|-最大匹配
最大团=补图的最大独立集

由题意可得，互相不认识的连边，构成一个二分图，ans=|V|-最大匹配，匈牙利算法。

/*poj 3692
  题意：
  已知班级有g个女孩和b个男孩，所有女生之间都相互认识，所有男生之间也相互认识，给出m对关系表示哪个女孩与哪个男孩认识。现在要选择一些学生来组成一个团，使得里面所有人都认识，求此团最大人数。
  限制：
  1 <= g,b <= 200; 0 <= m <= b*g
  思路：
  求最大团。
  最大独立集=|V|-最大匹配
  最大团=补图的最大独立集

  由题意可得，互相不认识的连边，构成一个二分图，ans=|V|-最大匹配，匈牙利算法。
 */
#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define PB push_back const int MAX_V=1005; int V; vector
      
        G[MAX_V]; int match[MAX_V]; bool used[MAX_V]; void add_edge(int u,int v){ G[u].PB(v); G[v].PB(u); } bool dfs(int v){ used[v]=true; for(int i=0;i