POJ 3692 最大独立集
题意：有G个女生，B个男生，所有的女生都互相认识，所有的男生都互相认识，还有N对男女，他们互相认识。
问从中选出最多的人数，是的他们全部互相认识。
思路：这道题的构图很巧妙，对于他的补图构图，对于所有互相认识的人，我们置Map[i][j] = 0 ,那么不认识的人置为1.
因为最大独立集中所有的点相互都没有边，即他们之间互相都认识，所以这道题就转化成了求最大独立集。
最大独立集=点数-最大匹配。
CODE：
#include <set>#include <map>#include <stack>#include <cmath>#include <queue>#include <cstdio>#include <string>#include <vector>#include <iomanip>#include <cstring>#include <iostream>#include <algorithm>#define Max 2505#define FI first#define SE second#define ll long long#define PI acos(-1.0)#define inf 0x3fffffff#define LL(x) ( x << 1 )#define bug puts("here")#define PII pair<int,int>#define RR(x) ( x << 1 | 1 )#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;int G , B , N ;int Map[444][444] ;bool vis[444] ;int link[444] ;bool find(int now){ for (int i = G + 1 ; i <= G + B ; i ++ ){ if(Map[now][i] && !vis[i]){ vis[i] = 1 ; if(link[i] == -1 || find(link[i])){ link[i] = now ;return 1 ; } } } return 0 ;}int main() { int ca = 0 ; while(cin >> G >> B >> N ,(G + B + N)){ mem(Map ,-1) ; mem(link ,-1) ; for (int i = 0 ; i < N ; i ++ ){ int s , t ; scanf("%d%d",&s,&t) ; Map[s][t + G] = 0 ;// Map[t + G][s] = 0 ; } int ans = 0 ; for (int i = 1 ; i <= G ; i ++ ){ mem(vis ,0) ; ans += find(i) ; } printf("Case %d: %d\n",++ ca ,G + B - ans) ; } return 0;}