首页 > 代码库 > POJ 3692 Kindergarten（二分图最大独立集）
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（二分图最大独立集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。