啊。。这次终于挑相互认识的小盆友出去玩咧。。呵呵。。
女生之间都相互认识，男生之间也是。给你男女认识对数，求出最大数量的小盆友相互都认识。。。
类似于之前那几道，建图，只不过这次匈牙利算法算的是未标记的图，在讨论里见这个叫补图。。。
开始一直不对因为，这个矩阵不是N*N的，因为我的初始化全是0，而最后判断的也是0的点才。。。所以界限需要严格定一下。。。
最后就用总人数减去不认识的最少人数（最小顶点覆盖）即可。
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> #define MAX 202 using namespace std; int map[MAX][MAX]; int used[MAX]; int mat[MAX]; int ng,nb; int Augement(int x) { int i; for(i=1; i<=nb; i++) if( !used[i] && map[x][i] == 0 ) { used[i] = 1; if( !mat[i] || Augement(mat[i]) ) { mat[i] = x; return 1; } } return 0; } int Hungary() { int i,sum = 0; memset(mat,0,sizeof(mat)); for(i=1; i<=ng; i++) { memset(used,0,sizeof(used)); if( Augement(i) ) sum++; } return sum; } int main() { int from,to,m; int ind = 1; while( ~scanf("%d%d%d",&ng,&nb,&m) ) { memset(map,0,sizeof(map)); if( ng == nb && ng == m && m == 0 ) break; while( m-- ) { scanf("%d%d",&from,&to); map[from][to] = 1; } int ans = Hungary(); printf("Case %d: %d/n",ind++,ng+nb-ans); } return 0; }
