首页 > 代码库 > 二分图的最大独立集 最大匹配解题 Hopcroft-Karp算法
二分图的最大独立集 最大匹配解题 Hopcroft-Karp算法
二分图模型中的最大独立集问题：在二分图G=(X,Y;E)中求取最小的顶点集V* ⊂ ｛X,Y｝,使得边 V*任意两点之间没有边相连。
公式： 最大独立集顶点个数 = 总的顶点数（|X|+|Y|）- 最大匹配数
poj3692
题意：幼儿园有G个小女孩和B个小男孩，小女孩彼此之间互相认识，小男孩彼此之间互相认识。一些小女孩与一些小男孩之间也互相认识。现在老师要选一些小朋友做一个游戏，这些小朋友之间必须互相认识。问老师最多可以选多少个小朋友。
解题：满足X集合，Y集合，E边集合的题目可以用二分图模型来解。此题中的E=｛(i,j)| i与j相互不认识｝。所有图初始为1，输入边则改为0。这样求最大匹配。
关于为什么要这样构图：X（Y）中都是相互认识的，也就是有关系的（有边相连）。但是二分图中X(Y)中的点之间是没有关系，是独立的点。所以建边的时候要反过来。
看看别人的博客怎么说： http://www.2cto.com/kf/201401/273879.html
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 8 const int N=1005,INF=0x3f3f3f3f; 9 int bmap[N][N],cx[N],cy[N],dx[N],dy[N];10 bool bmask[N];11 int nx,ny,dis,ans;12 bool searchpath()13 {14 queue<int> q;15 dis=INF;16 memset(dx,-1,sizeof(dx));17 memset(dy,-1,sizeof(dy));18 for(int i=1;i<=nx;i++)19 {20 if(cx[i]==-1){ q.push(i); dx[i]=0; }21 while(!q.empty())22 {23 int u=q.front(); q.pop();24 if(dx[u]>dis) break;25 for(int v=1;v<=ny;v++)26 {27 if(bmap[u][v]&&dy[v]==-1)28 {29 dy[v]= dx[u] + 1;30 if(cy[v]==-1) dis=dy[v];31 else32 {33 dx[cy[v]]= dy[v]+1;34 q.push(cy[v]);35 }36 }37 }38 }39 }40 return dis!=INF;41 }42 int findpath(int u)43 {44 for(int v=1;v<=ny;v++)45 {46 if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1)47 {48 bmask[v]=1;49 if(cy[v]!=-1&&dy[v]==dis) continue;50 if(cy[v]==-1||findpath(cy[v]))51 {52 cy[v]=u; cx[u]=v;53 return 1;54 }55 }56 }57 return 0;58 }59 void maxmatch()60 {61 ans=0;62 memset(cx,-1,sizeof(cx));63 memset(cy,-1,sizeof(cy));64 while(searchpath())65 {66 memset(bmask,0,sizeof(bmask));67 for(int i=1;i<=nx;i++)68 if(cx[i]==-1) ans+=findpath(i);69 }70 }71 int main()72 {73 //freopen("test.txt","r",stdin);74 int m,i,j,k=1,cas;75 while(scanf("%d%d%d",&nx,&ny,&m)!=EOF)76 {77 if(!nx) break;78 for(i=1;i<=nx;i++)79 for(j=1;j<=ny;j++)80 bmap[i][j]=1;81 while(m--)82 {83 scanf("%d%d",&i,&j);84 bmap[i][j]=0;85 }86 maxmatch();87 printf("Case %d: ",k++);88 printf("%d\n",nx+ny-ans);89 }90 return 0;91 }
二分图的最大独立集 最大匹配解题 Hopcroft-Karp算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。