[HDU2444] The Accomodation of Students

2017年10月9日

题意,有一些学生,他们中的一部分互相认识,比如,A和B互相认识,B和C互相认识,但是这不意味着A和C是认识的。互相认识的一对学生可以分到一间房。

现在要求你把他们分成两组,每组中的任意两人互相不认识,而两组间的人互相认识,如果不能分则输出“No”,否则输出最多能分到几间房。

二分图最大匹配问题,先用bfs判断是否为二分图,判断方法是染色法,从任意一点出发,所能到达相邻点都与该点的颜色不同则为二分图,若有相同则不是二分图。

然后用dfs求最大匹配数。

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n, m;
vector<int> G[N];
int link[N], vis[N];
int dfs(int u)
{
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (vis[v])
      continue;
    vis[v] = 1;
    if (link[v] == -1 || dfs(link[v])) {
      link[v] = u;
      return 1;
    }
  }
  return 0;
}
int bfs()
{
  memset(vis, 0, sizeof(vis));
  memset(link, -1, sizeof(link));
  queue<int> que;
  que.push(1);
  vis[1] = 1;
  link[1] = 0;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i = 0; i < G[u].size(); i++) {
      int v = G[u][i];
      if (!vis[v]) {
        link[v] = 1 - link[u];
        vis[v] = 1;
        que.push(v);
      } else if (link[v] == link[u]) {
        return 0;
      }
    }
  }
  return 1;
}
int main()
{
  while (~scanf("%d %d", &n, &m)) {
    for (int i = 0; i < N; i++)
      G[i].clear();
    for (int i = 0; i < m; i++) {
      int u, v;
      scanf("%d %d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
    }
    if (!bfs()) {
      puts("No");
      continue;
    }
    memset(link, -1, sizeof(link));
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
      memset(vis, 0, sizeof(vis));
      cnt += dfs(i);
    }
    printf("%d\n", cnt / 2);
  }
  return 0;
}

发表评论

您的电子邮箱地址不会被公开。