锐客网

  1. 首页 > it技术 > >

poj 3692 Kindergarten（最大独立点集 + 二分图最大匹配）

http://poj.org/problem?id=3692
题意：在幼儿园中，有许多小孩。其中有男孩，也有女孩。女孩之间相互认识，男孩之间也相互认识。同时，一些男孩和女孩之间也相互认识，有一天，老师希望从所有人之中选出一些人来玩游戏，这个游戏需要所有的参与者之间相互认识，问老师可以最多找出多少人来玩这个游戏。


思路：


如果将男孩女孩看做顶点，男女之间的认识关系看做边，那么本题就转化为在图中求一个最大完全子图（最大团）的规模。但是在本题有特殊条件，男孩之间相互认识，女孩之间相互认识，即男孩和女孩本身就是两个完全子图，同时，如果将男孩和女孩看做集合，不能直接选取认识关系做边，因为这样违反了二分图的定义。那么我们可以采用认识关系的补集作为边，X= {男孩集合}， Y= {女孩集合}， E= {（i,j）| 男孩i与女孩j之间相互不认识}， 构建二分图G= {X,Y,E}。


最大独立集：从二分图G= （X,Y,E）中选取一些点V*（属于X+Y），使得点集V*中任意两点之间没有边相连。
最大独立点集元素个数 = 节点数（X+Y） - 最大匹配数；


由于E是认识关系的补集构成，那么该二分图的最大独立集元素的个数等价于原图中最大完全子图的顶点数。
因此我们只需构造这样的二分图，利用匈牙利算法求出最大匹配数，得到最大独立集顶点个数就是答案。
【poj 3692 Kindergarten（最大独立点集 + 二分图最大匹配）】


#include #include const int maxn = 210; int n,m,k; bool map[maxn][maxn]; bool a[maxn][maxn]; int match[maxn]; int chk[maxn]; bool dfs(int p) { for(int i = 1; i <= m; i++) { if(map[p][i] && !chk[i]) { chk[i] = 1; if(match[i] == -1 || dfs(match[i])) { match[i] = p; return true; } } } return false; }int main() { int test = 1; while(~scanf("%d %d %d",&n,&m,&k)) { if(n == 0 && m == 0 && k == 0) break; memset(map,false,sizeof(map)); memset(a,false,sizeof(a)); int x,y; for(int i = 0; i < k; i++) { scanf("%d %d",&x,&y); a[x][y] = true; }for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(!a[i][j]) map[i][j] = true; } }memset(match,-1,sizeof(match)); int res = 0; for(int i = 1; i <= n; i++) { memset(chk,0,sizeof(chk)); if(dfs(i)) res += 1; }printf("Case %d: %d\n",test++,n+m-res); } return 0; }








    推荐阅读


    上一篇：问题修复记录|问题解决（struts版本升级为2.5.22，struts某些action扫描不进，调用action报404错）

    下一篇：Lombok入门