首页 > 代码库 > POJ3692 Kindergarten 【最大独立集】

POJ3692 Kindergarten 【最大独立集】

2024-07-26 20:00:19   219人阅读

Kindergarten
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 5317 Accepted: 2589

Description

In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys know each other. Now the teachers want to pick some kids to play a game, which need that all players know each other. You are to help to find maximum number of kids the teacher can pick.

Input

The input consists of multiple test cases. Each test case starts with a line containing three integers
G, B (1 ≤ G, B ≤ 200) and M (0 ≤ M ≤ G × B), which is the number of girls, the number of boys and
the number of pairs of girl and boy who know each other, respectively.
Each of the following M lines contains two integers X and Y (1 ≤ X≤ G,1 ≤ Y ≤ B), which indicates that girl X and boy Y know each other.
The girls are numbered from 1 to G and the boys are numbered from 1 to B.

The last test case is followed by a line containing three zeros.

Output

For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the maximum number of kids the teacher can pick.

Sample Input

2 3 3
1 1
1 2
2 3
2 3 5
1 1
1 2
2 1
2 2
2 3
0 0 0

Sample Output

Case 1: 3
Case 2: 4

Source

2008 Asia Hefei Regional Contest Online by USTC

题意：在幼儿园中，所有男孩间都相互认识，女孩彼此也都认识，有一些男孩跟一些女孩认识，现在给定这些认识关系，选定一个最大的点集使得里面每个人都相互认识。

题解：二分图的独立集只从二分图G = （X,Y;E）选取一些点v属于{X, Y}，使得点集v中任意两点间没有通过边链接。而二分图的最大独立集模型就是求取max|v|。有如下公式：

   最大独立集顶点个数 = 节点数（|X|+|Y|）- 最大匹配数。

#include <stdio.h>
#include <string.h>

#define maxn 205

bool G[maxn][maxn], visy[maxn];
int girl[maxn], boy[maxn];
int g, b, m, cas = 1;

void getMap() {
    int u, v;
    memset(G, 0, sizeof(G));
    while(m--) {
        scanf("%d%d", &u, &v);
        G[u][v] = true;
    }
}

int findPath(int x) {
    int i;
    for(i = 1; i <= b; ++i) {
        if(!G[x][i] && !visy[i]) {
            visy[i] = 1;
            if(boy[i] == -1 || findPath(boy[i])) {
                boy[i] = x; return 1;
            }
        }
    }
    return 0;
}

int MaxMatch() {
    int i, ans = 0;
    memset(girl, -1, sizeof(girl));
    memset(boy, -1, sizeof(boy));
    for(i = 1; i <= g; ++i) {
        memset(visy, 0, sizeof(visy));
        ans += findPath(i);
    }
    return ans;
}

void solve() {
    printf("Case %d: %d\n", cas++, g + b - MaxMatch());
}

int main() {
    while(scanf("%d%d%d", &g, &b, &m), g | b | m) {
        getMap();
        solve();
    }
    return 0;
}


POJ3692 Kindergarten 【最大独立集】


联系
我们