题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2444
题意：有n个学生，有m对人是认识的，每一对认识的人能分到一间房，问能否把n个学生分成两部分，每部分内的学生互不认识，而两部分之间的学生认识。如果可以分成两部分，就算出房间最多需要多少间，否则就输出No。
首先判断是否为二分图，然后判断最大匹配
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int maxn = 205; int head[maxn], vis[maxn], matching[maxn]; bool check[maxn]; int eid; struct Edge { int u, v, nxt; Edge(){} Edge(int from, int to, int nx):u(from), v(to), nxt(nx){} }edge[maxn*maxn]; inline void AddEdge(int u, int v) { edge[eid] = Edge(u, v, head[u]); head[u] = eid++; edge[eid] = Edge(v, u, head[v]); head[v] = eid++; } bool judge(int n) { memset(vis, -1, sizeof(vis)); queue<int> q; for(int i = 1; i <= n; i++) { if(vis[i] == -1) { q.push(i); vis[i] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(int j = head[u]; j != -1; j = edge[j].nxt) { int v = edge[j].v; if(vis[v] == -1) { vis[v] = !vis[u]; q.push(v); } else if(vis[v] == vis[u]) return false; } } } } return true; } bool dfs(int u) { for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].v; if(!check[v]) { check[v] = true; if(matching[v] == -1 || dfs(matching[v])) { matching[u] = v; matching[v] = u; return true; } } } return false; } int hungarian(int n) { int ans = 0; memset(matching, -1, sizeof(matching)); for(int i = 1; i <= n; i++) { if(matching[i] == -1) { memset(check, false, sizeof(check)); if(dfs(i)) ans++; } } return ans; } int main() { int n, m; while(scanf("%d%d", &n, &m) != EOF) { eid = 0; memset(head, -1, sizeof(head)); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); AddEdge(u, v); } if(judge(n)) printf("%d\n", hungarian(n)); else printf("No\n"); } return 0; }