poj 3692 二分圖最大匹配

poj 3692 二分圖最大匹配

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