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\n",++tcase,G+B-dd);

    }

}

巴特西

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

最新文章

热门文章