最大独立集，把不认识的男女看成是有矛盾的，要选出一些互相没有矛盾的男女。
View Code #include#include #include #include using namespace std;#define maxn 205bool g[maxn][maxn];int uN, vN, m;int xM[maxn], yM[maxn];bool chk[maxn];void input(){ for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); g[--a][--b] = true; } for (int i = 0; i < uN; i++) for (int j = 0; j < vN; j++) g[i][j] = !g[i][j];}bool SearchPath(int u){ int v; for (v = 0; v < vN; v++) if (g[u][v] && !chk[v]) { chk[v] = true; if (yM[v] == -1 || SearchPath(yM[v])) { yM[v] = u; xM[u] = v; return true; } } return false;}int MaxMatch(){ int u, ret = 0; memset(xM, -1, sizeof(xM)); memset(yM, -1, sizeof(yM)); for (u = 0; u < uN; u++) { if (xM[u] == -1) { memset(chk, false, sizeof(chk)); if (SearchPath(u)) ret++; } } return ret;}int main(){ //freopen("t.txt", "r", stdin); int t = 0; while (scanf("%d%d%d", &uN, &vN, &m), uN | vN | m) { t++; memset(g, 0, sizeof(g)); input(); printf("Case %d: %d\n", t, uN + vN - MaxMatch()); } return 0;}