The Accomodation of Students

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1901    Accepted Submission(s): 911

4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6

No
3

这道题要先判断图是不是二分图，如果不是的话，就直接输出No,是的话就求最大匹配，

建边是双向的所以要除以2。

先判断能否构成二分图，判断二分图用交叉染色法从某个未染色的点出发把此点染成白

色，该点周围的点染成黑色黑色周围的又染成白色，若走到某个点已经染色并且它相邻

点的颜色与它一样则不是二分图，而是有奇数圈的图可以这样理解，染白色既加入X集

合，黑色既加入Y集合若某个点即是X集合又是Y集合，那说明不是二分图。

如1和2、3是认识，则1应该在一边，2和3在另一边才满足二分图；
但2和3又认识，则2、3不能在一边；故此种情况不是二分图；

#include"stdio.h"
#include"string.h"
#include"iostream"
#include"queue"
using namespace std;
#define N 205
int mark[N],link[N],map[N][N],color[N],n;
int find(int a)       //匈牙利算法
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(!mark[i]&&map[a][i])
		{
			mark[i]=1;
			if(!link[i]||find(link[i])) //若i已经配对，则查找和i配对的那个元素是否还能和其他元素配对
			{
				link[i]=a; //若可以则把i配给a
				return 1;
			}
		}
	}
	return 0;
}
int judge()        //判断是否是二分图
{
	int i,cur;
	queue<int>q;       //队列声明
	q.push(1);       //把1加入队列
	while(!q.empty())
	{
		cur=q.front();      //取队首元素
		q.pop();             //删除队首元素
		for(i=1;i<=n;i++)
		{
			if(map[cur][i])      //1和2、3认识则把2、3均标记为2；   
			{
				if(color[i]==-1)      
				{
					color[i]=1-color[cur];
					q.push(i);
				}
				else if(color[i]==color[cur])      //接下来到2出对时，color[3]=color
					return 0;
			}
		}
	}
	return 1;
}
int main()
{
	int i,j,m,ans;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		memset(link,0,sizeof(link));
		memset(map,0,sizeof(map));
		memset(color,-1,sizeof(color));
		while(m--)
		{
			scanf("%d%d",&i,&j);
			map[i][j]=map[j][i]=1;
		}
		if(judge()==0)
		{
			printf("No\n");
			continue;
		}
		ans=0;
		for(i=1;i<=n;i++)
		{
			memset(mark,0,sizeof(mark));
			ans+=find(i);
		}
		printf("%d\n",ans/2);
	}
	return 0;
}



hdu 2444 The Accomodation of Students,布布扣,bubuko.com
hdu 2444 The Accomodation of Students
原文：http://blog.csdn.net/u011721440/article/details/21030611