题意：有一些男生女生互相了解，要求选出最大的学生之间互相了解。
思路：只需要将不了解的学生之间建边就可转化成最大独立集问题 ： 结点数-二分图最大匹配。 直接套模版就可
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-20 01:24 5 * Filename : poj_3692.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 402; 34 int g, b, m, n; 35 vector<int> Map[LEN]; 36 int match[LEN], vis[LEN], mp[LEN][LEN]; 37 38 bool dfs(int v){ 39 vis[v] = 1; 40 for(int i=0; i<Map[v].size(); i++){ 41 int u = Map[v][i], w = match[u]; 42 if(w < 0 || !vis[w] && dfs(w)){ 43 match[v] = u; 44 match[u] = v; 45 return true; 46 } 47 } 48 return false; 49 } 50 51 int hungary(){ 52 int ret = 0; 53 memset(match, -1, sizeof match); 54 for(int v = 0; v < n; v++){ 55 if( match[v] < 0){ 56 memset(vis, 0, sizeof vis); 57 if(dfs(v)) ret++; 58 } 59 } 60 return ret; 61 } 62 63 int main() 64 { 65 // freopen("in.txt", "r", stdin); 66 67 int fr, to, kase = 1; 68 while(scanf("%d%d%d", &g, &b, &m)){ 69 if(!g && !b && !m) break; 70 for(int i=0; i<LEN; i++) Map[i].clear(); 71 memset(mp, 0, sizeof mp); 72 for(int i=0; i<m; i++){ 73 scanf("%d%d", &fr, &to); 74 fr--, to--; 75 mp[fr][to+g] = mp[to+g][fr] = 1; 76 } 77 n = g+b; 78 for(int i=0; i<g; i++){ 79 for(int j=g; j<n; j++){ 80 if(i == j) continue; 81 if(!mp[i][j]) Map[i].PB(j); 82 } 83 } 84 int ans = n-hungary(); 85 printf("Case %d: %d ", kase++, ans); 86 } 87 return 0; 88 }