题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2444
题意是有n个人，m个配对，问能不能根据m个将这些人分成两个集合，且集合中的任意两人没有配对，其实这也就是二分图的定义。
思路就是首先我们要用染色法判断一下这个图能不能构成一个二分图，就是让每个点为起点跑一遍bfs，判断颜色有没有冲突，有冲突的话就不能构成一个二分图，如果是一个二分图的话，就直接用匈牙利算法求最大匹配数就好了。因为二分图应该是一个图的两个集合，一半去匹配另一半的，但是这里我都是在一个图里去匹配的，也就是让1-n去匹配1-n，所以最终的结果要除以2。存图方式我用的是vector，然后在写的过程中我用了邻接矩阵的方式进行的操作，然后就wa到怀疑人生，重写了好多遍都没过....
AC代码：
代码语言：javascript复制#include <bits/stdc .h>
#define maxn 205
using namespace std;
vector<int> G[maxn];
int col[maxn];
int vis[maxn];
int pre[maxn];
int n,m;
void init(){
for(int i=0;i<=n;i ){
G[i].clear();
}
}
bool bfs(int s){
queue<int> q;
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(int i=0;i<G[v].size();i ){
int xx = G[v][i];
if(col[xx] == 0){
col[xx] = -col[v];
q.push(xx);
}
if(col[xx] == col[v]){
return false;
}
}
}
return true;
}
bool dfs(int x){
for(int i=0;i<G[x].size();i ){
int v = G[x][i];
if(vis[v] == 0){
vis[v] = 1;
if(pre[v] == -1 || dfs(pre[v])){
pre[v] = x;
return true;
}
}
}
return false;
}
int Fun(){
int sum = 0;
memset(pre,-1,sizeof(pre));
for(int i=1;i<=n;i ){
memset(vis,0,sizeof(vis));
if(dfs(i)) sum ;
}
return sum;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
init();
for(int i=0;i<m;i ){
int s,t;
scanf("%d%d",&s,&t);
G[s].push_back(t);
G[t].push_back(s);
}
memset(col,0,sizeof(col));
bool flag = true;
for(int i=1;i<=n;i ){
if(col[i] == 0){
col[i] = 1;
if(!bfs(i)){
flag = false;
break;
}
}
}
if(flag){
int ans = Fun();
printf("%dn",ans / 2);
}
else{
puts("No");
}
}
return 0;
}
