The Accomodation of Students
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4672 Accepted Submission(s): 2142
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个关系，表示a认识b，首先要将n个人分成两组，每组内满足任意选取两个人他们都互相不认识。如果不能够分成两组输出NO，如果能够分成两组，那么再让两个互相认识的人分到一个double rooms里边，问最多能够分出多少个double rooms的组合。
思路：
1、首先对于分成两组的操作，明显就是在问你这个给出的图是否满足一个二分图，如果不满足二分图，那么就输出No，我们这里采用二分图染色的方法来解决这个问题：
假如1认识2，2认识3,3认识1。
我们先对1染色成1,2就一定要染色为2，相应的如果2染色为2，那么3一定要染色为1，但是3和1颜色相同，但是3还认识1，那么就不满足二分图，根据这个特性，我们直接对其BFS染色即可。
2、对于最多能够分出多少个double rooms的组合问题，我们直接求一遍最大二分匹配数即可。
AC代码：
</pre><pre name="code" class="cpp">#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
vector<int >mp[2000];
int color[2000];
int vis[2000];
int match[2000];
int n,m;
int find(int x)
{
vis[x]=1;
for(int i=0;i<mp[x].size();i++)
{
int v=mp[x][i];
if(vis[v]==0)
{
vis[v]=1;
if(match[v]==-1||find(match[v]))
{
match[v]=x;
return 1;
}
}
}
return 0;
}
int Bfs_color(int x)
{
queue<int >s;
s.push(x);
color[x]=1;
while(!s.empty())
{
int u=s.front();
s.pop();
for(int j=0;j<mp[u].size();j++)
{
int v=mp[u][j];
if(color[v]==0)
{
color[v]=3-color[u];
s.push(v);
}
else
{
if(color[v]==color[u])return 0;
}
}
}
return 1;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(color,0,sizeof(color));
memset(match,-1,sizeof(match));
for(int i=1;i<=n;i++)mp[i].clear();
int root=1;
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
root=x;
mp[x].push_back(y);
mp[y].push_back(x);
}
int tt=Bfs_color(root);
if(tt==0)
{
printf("No\n");
}
else
{
int output=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(find(i))output++;
}
printf("%d\n",output/2);
}
}
}