hdu 1068 Girls and Boys（二分图求最大独立集合）

Girls and Boys

Time Limit: 20000/10000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3260????Accepted Submission(s): 1405

#include <iostream>#include <stdio.h>#include <memory.h>using namespace std;const int N = 1005;int pre[N];bool map[N][N], flag[N];int n;int find(int cur) //匈牙利算法{ int i; for(i = 0; i < n; i++) { if(map[cur][i] && !flag[i]) { flag[i] = true; if(pre[i] == -1 || find(pre[i])) { pre[i] = cur; return 1; } } } return 0;}int main(){ int i, j, r, k, num, sum; while(scanf("%d", &n) != EOF) { memset(map, false, sizeof(map)); memset(pre, -1, sizeof(pre)); for(i = 0; i < n ; i++) { scanf("%d: (%d)", &k, &num); //输入格式注意！ for(j = 0; j < num; j++) { scanf("%d", &r); map[k][r] = true; //建表时 } } sum = 0; for(i = 0; i < n; i++) { memset(flag, false, sizeof(flag)); sum += find(i); } sum /= 2; //二分图具有对称性，最大匹配数 /= 2 //二分图最大独立集合 = 节点数 - 最大匹配数 printf("%d\n", n - sum); } return 0;}?