题目：The Accomodation of Students
总结：给出n个点m个边，如果不是二分图输出No，否则输出最大匹配数 用染色法判断是否是二分图，先给一个点取一种颜色，再给和它相邻的点的取另一种颜色，这样反复的取，如果有了冲突，说明不是二分图。用匈牙利算法求最大匹配数。
#include <stdio.h> #include <vector> #include <string.h> using namespace std; const int N = 205; vector<int>G[N]; int n,m; int vis[N],pre[N]; int c[N]; //用染色法判断这个图是否是二分图 bool Dfs(int u,int colour){ c[u] = colour; for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(c[v] == 0 && Dfs(v,3-colour)){ return true; }else if(c[v] != 3-colour) { printf("No\n"); return true; } } return false; } //用匈牙利算法求出最大匹配数 bool dfs(int u){ for(int i = 0;i <G[u].size();i++){ int v = G[u][i]; if(!vis[v]){ vis[v] = 1; if(!pre[v] || dfs(pre[v])){//如果前一个可以移动也行 pre[v] = u;//记录前一个 return true; } } } return false; } void solve(){ for(int i = 1;i <= n;i++){ if(c[i] == 0 && Dfs(i,1)){ return; } } int ans = 0; for(int i = 1;i <= n;i++){ memset(vis,0,sizeof vis); if(dfs(i)) ans++; } printf("%d\n",ans); } void init(){ for(int i = 0;i < N;i++){ G[i].clear(); } memset(pre,0,sizeof pre); memset(c,0,sizeof c); } int main(){ while(~scanf("%d%d",&n,&m)){ init(); while(m--){ int x,y; scanf("%d%d",&x,&y); G[x].push_back(y); } solve(); } return 0; }