hdu 2458 Kindergarten 匹配

hdu 2458 Kindergarten 匹配

题目大意：幼儿园中所有的男孩之间都互相认识，所有的女孩都互相认识，男孩和女孩之间有一部分互相认识，求一个最大完全子图（最大团），即去一些顶点，使得他们之间都互相认识，并使取出的节点数最多。

男孩和女孩本身就是完全子图，将女孩看成一个集合，男孩看成一个集合，不能直接选择认识关系作为边集（因为这样不符合二分图定义），所以选认识关系的补集作为边集，即在不认识的人之间连边，则最大完全子图即即对应最大点独立集。即求最大点独立集。

最大点独立集个数=顶点数-点覆盖数，点覆盖数=匹配数。

#include <stdio.h>
#include <string.h>
#define maxn 500
int nx,ny;
int g[maxn][maxn],ans,sx[maxn],sy[maxn];
int cx[maxn],cy[maxn];
int path(int u)
{sx[u]=1;int v;for(v=1;v<=ny;v++){if(g[u][v]>0&&!sy[v]){sy[v]=1;if(!cy[v]||path(cy[v])){cx[u]=v;cy[v]=u;return 1;}}}return 0;
}
int solve()
{ans=0;int i;memset(cx,0,sizeof(cx));memset(cy,0,sizeof(cy));for(i=1;i<=nx;i++){if(!cx[i]){    memset(sx,0,sizeof(sx));memset(sy,0,sizeof(sy));ans+=path(i);}}return 0;
}int main()
{int tot=1;int m,i;int x,y;while(1){memset(g,1,sizeof(g));scanf("%d%d%d",&nx,&ny,&m);if(nx==0&&ny==0&&m==0)break;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);g[x][y]=0;}solve();printf("Case %d: %dn",tot,nx+ny-ans);tot++;}return 0;
}

转载于:.html