POJ 3692 Kindergarten（二分图最大独立集）

题意：

有G个女孩，B个男孩。女孩彼此互相认识，男孩也彼此互相认识。有M对男孩和女孩是认识的。分别是(g1,b1),.....(gm,bm)。

现在老师要在这G+B个小孩中挑出一些人，条件是这些人都互相认识。问最多可以挑出多少人。

思路：

女孩之间互相认识，男孩之间互相认识，所以我们可以将连边定义为：不认识。即：若两个节点之间有连边，则两个节点互不认识。

故题意即为选出最多的点使得这些点任意两点之间没有连边。即选最少的点覆盖所有边。（二分图最大独立集/二分图最小点覆盖）

代码：

vector<int> graph[205];
int cx[205],cy[205];
bool bmask[205];
int G,B,M;
bool mp[205][205];


int findPath(int u){
    int L=graph[u].size();
    rep(i,0,L-1){
        int v=graph[u][i];
        if(!bmask[v]){
            bmask[v]=true;
            if(cy[v]==-1||findPath(cy[v])){
                cy[v]=u;
                cx[u]=v;
                return 1;
            }
        }
    }
    return 0;
}
int MaxMatch(){
    int ans=0;
    rep(i,1,G) cx[i]=-1;
    rep(i,1,B) cy[i]=-1;
    rep(i,1,G) if(cx[i]==-1){
        mem(bmask,false);
        ans+=findPath(i);
    }
    return ans;
}


int main(){
    int tcase=0;
    while(scanf("%d%d%d",&G,&B,&M)!=EOF){
        if(!G && !B && !M) break;

        rep(i,1,G) graph[i].clear();
        mem(mp,false);

        while(M--){
            int x,y;
            scanf("%d%d",&x,&y);
            mp[x][y]=true;
        }
        rep(i,1,G) rep(j,1,B) if(false==mp[i][j]) graph[i].push_back(j);

        int dd=MaxMatch();
        printf("Case %d: %d
",++tcase,G+B-dd);
    }
}