POJ 3692 Kindergarten
题意:一个班级内,男的都互相认识,女的都互相认识,现在有k对男女互相认识,要求选出最多的人,使得他们两两互相认识
思路:最大独立集,把不认识的连边,就可以求出最大独立集就是两两互相认识的
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 205; int G, B, k, graph[N][N]; vector<int> g[N]; int left[N], vis[N]; bool 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 (!left[v] || dfs(left[v])) { left[v] = u; return true; } } return false; } int hungary() { int ans = 0; memset(left, 0, sizeof(left)); for (int i = 1; i <= G; i++) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ans++; } return ans; } int main() { int cas = 0; while (~scanf("%d%d%d", &G, &B, &k) && G) { int u, v; memset(graph, 0, sizeof(graph)); while (k--) { scanf("%d%d", &u, &v); graph[u][v] = 1; } for (int i = 1; i <= G; i++) { g[i].clear(); for (int j = 1; j <= B; j++) { if (graph[i][j]) continue; g[i].push_back(j); } } printf("Case %d: %d\n", ++cas, G + B - hungary()); } return 0; }