本文主要是介绍HDU-2444 二分图的判别和最大匹配数。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
n个人，有m对关系，问你能否把他们分成两组，使得他们任意两两之间都不相互认识。如果不能输出“No”否则，问你，他们之间最最多认识的人。
分析：
题意很明了，一个时要我们判断他们之间能否构成 二分图，另外求二分图的最大匹配数。
关于判断二分图。一个最基本的方法就是染色法，意思是：把他们有关系的用两种不同颜色染色。通过邻接矩阵搜索，如果有一对有关系，并且颜色是相同的。那么就不是二分图了。
二分匹配有两种算法，一种是匈牙利算法和Hopcroft算法。其前面是每次寻找一条增广路，时间复杂度为(v*E)，而后面的是在匈牙利算法进行了改进，每次不止一次增广一个非饱和顶点,时间复杂度为(E*V^0.5),稍比前面快点。
匈牙利算法(47ms)
#include<stdio.h>
#include<string.h>
#define N 250
int used[N],match[N],rec[N];
int map[N][N],n,m,flag;void DFS(int i,int color)
{for(int j=1;j<=n;j++){if(map[i][j]){if(rec[j]==0){rec[j]=-color;DFS(j,-color);}else if(rec[j]==color){flag=false;return ;}if(flag==false)return ;}}
}bool find(int i)
{for(int j=1;j<=n;j++){if(map[i][j]&&!used[j]){used[j]=1;if(!match[j]||find(match[j])){match[j]=i;return true;}}}return false;
}int main()
{int k,x,y;while(scanf("%d %d",&n,&m)!=EOF){memset(map,0,sizeof(map));memset(rec,0,sizeof(rec));flag=true;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);map[x][y]=map[y][x]=1;}DFS(1,1);if(!flag){puts("No");continue;} int ans=0;memset(match,0,sizeof(match));for(int i=1;i<=n;i++){memset(used,0,sizeof(used));if(find(i))ans++;}printf("%d\n",ans/2);}return 0;
}Hopcroft 算法(47ms) 由于测试数据不多，时间相差不多。
#include<cstdio>
#include<queue>
#include<cstring>
#define INF 1<<29
using namespace std;
const int N=250;
int vis[N],dx[N],dy[N],Mx[N],My[N];
int g[N][N],rec[N];
int n,m,dis,flag;void check(int i,int color)
{for(int j=1;j<=n;j++){if(g[i][j]){if(!rec[j]){rec[j]=-color;check(j,-color);}else if(rec[j]==color){flag=false;return;}if(flag==false) return;}}
}bool searchp()
{queue<int>Q;dis=INF;memset(dx,-1,sizeof(dx));memset(dy,-1,sizeof(dy));for(int i=1;i<=n;i++)if(Mx[i]==-1){Q.push(i); //多条增广。 dx[i]=0;}while(!Q.empty()){int u=Q.front();Q.pop();if(dx[u]>dis) break;for(int v=1;v<=n;v++)if(g[u][v]&&dy[v]==-1){dy[v]=dx[u]+1;if(My[v]==-1) dis=dy[v];else{dx[My[v]]=dy[v]+1;Q.push(My[v]);}}}return dis!=INF;
}bool DFS(int u)
{for(int v=1;v<=n;v++){if(!vis[v]&&g[u][v]&&dy[v]==dx[u]+1){vis[v]=1;if(My[v]!=-1&&dy[v]==dis) continue;if(My[v]==-1||DFS(My[v])){My[v]=u;Mx[u]=v;return true;}}}return false;
}int MaxMatch()
{int res=0;memset(Mx,-1,sizeof(Mx));memset(My,-1,sizeof(My));while(searchp()){memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)if(Mx[i]==-1&&DFS(i)) res++;}return res;
}int main()
{int x,y;while(~scanf("%d %d",&n,&m)){memset(g,0,sizeof(g));memset(rec,0,sizeof(rec));flag=true;for(int j=0;j<m;j++){scanf("%d %d",&x,&y);g[x][y]=g[y][x]=1;}check(1,1);if(!flag){puts("No");continue;}printf("%d\n",MaxMatch()/2); }return 0;
}/*
5 5
3 5
2 1
4 5
3 2
1 5
*/这篇关于HDU-2444 二分图的判别和最大匹配数。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
