POJ 3692 最大独立集 - c++编程基础

题意：有G个女生，B个男生，所有的女生都互相认识，所有的男生都互相认识，还有N对男女，他们互相认识。

问从中选出最多的人数，是的他们全部互相认识。

思路：这道题的构图很巧妙，对于他的补图构图，对于所有互相认识的人，我们置Map[i][j] = 0 ,那么不认识的人置为1.

因为最大独立集中所有的点相互都没有边，即他们之间互相都认识，所以这道题就转化成了求最大独立集。

最大独立集=点数-最大匹配。

CODE：

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#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  
#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;  
}