hdu 2444 The Accomodation of Students(二分匹配匈牙利算法邻接表实现)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

The Accomodation of Students
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3565 Accepted Submission(s): 1659
Problem Description
There
are a group of students. Some of them may know each other, while others
don't. For example, A and B know each other, B and C know each other.
But this may not imply that A and C know each other.
Now you are
given all pairs of students who know each other. Your task is to divide
the students into two groups so that any two students in the same group
don't know each other.If this goal can be achieved, then arrange them
into double rooms. Remember, only paris appearing in the previous given
set can live in the same room, which means only known students can live
in the same room.
Calculate the maximum number of pairs that can be arranged into these double rooms.

Input
For each data set:
The
first line gives two integers, n and m(1<n<=200), indicating
there are n students and m pairs of students who know each other. The
next m lines give such pairs.
Proceed to the end of file.

Output
If
these students cannot be divided into two groups, print "No".
Otherwise, print the maximum number of pairs that can be arranged in
those rooms.

Sample Input
4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6

Sample Output
No
3

Source
2008 Asia Harbin Regional Contest Online

题意：有n个人，m条关系，问通过这些关系判断，所有人是否可以分成两个组，如果可以則求出一组最多多少人。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>
#define ll long long using namespace std; const int N = ;
int head[N],total,visit[N];
int link[N],color[]; struct nodes
{
int e,next;
} Edge[N]; void add(int x,int y)//加边，邻接表形式建图
{
Edge[total].e = y;
Edge[total].next = head[x];
head[x] = total++;
} int dfs(int f) //匈牙利算法中的二分匹配dfs实现
{
for(int i = head[f]; i != -; i = Edge[i].next)//邻接表遍历与起始点f相连的所有点
{
int s = Edge[i].e; //与起始点相连的点
if(visit[s]) continue;//访问过就跳过
visit[s] = ;
if(link[s] == - || dfs(link[s]))//寻找增广路径
{
link[s] = f ;
return ;
}
}
return ;
} void init()//初始化
{
total = ;
memset(head,-,sizeof(head));
memset(link,-,sizeof(link));
}
bool bcolor(int u,int x)
{
if(color[u] != -)//如果从上个点出发过来，发现该点已染色
{
if(color[u] == x)//如果此点颜色与邻点相同
return false; //不是二分图，返回染色失败
}
else
{
color[u] = x^;//该点未染色，則染与上个点不同的颜色
for(int i = head[u]; i != -; i = Edge[i].next)//遍历与该点相连的所有边
{
if(!bcolor(Edge[i].e,color[u]))//如果下一层染色失败，則返回失败
return false;
}
}
return true;
}
bool judge(int n)
{
memset(color,-,sizeof(color));//先初始化所有点为-1,代表未染色
for(int i = ; i <= n; i++)//依次检查点是否染过色
{
if(color[i] == -)//若没访问过，則开始填色
{
if(!bcolor(i,))
return false;
}
}
return true;
}
int main(void)
{
int n,i,cnt,m;
while(scanf("%d",&n) != -)
{
init();
scanf("%d",&m);
for(i = ; i < m; i++)
{
int x,y;
scanf("%d %d",&x,&y);
add(x,y);
//add(y,x);
}
if(!judge(n)) // 判断是否为二分图
{
printf("No\n");
}
else //匈牙利算法
{
for(cnt = ,i = ; i <= n; i++)
{
memset(visit,,sizeof(visit));
if(dfs(i))
cnt++;
}
printf("%d\n",cnt);//若建的双向边則最大匹配数统计了两次，因为是双向的，所以需除以2 ；若建的单向边，則不需要除以2.
} }
return ;
}