HDU 2444 The Accomodation of Students(二分图判断+最大匹配数)

#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("%d\n",ans / 2);
    }
    else{
      puts("No");
    }
  }
  return 0;
}