首页 > 代码库 > POJ 3692-Kindergarten(二分图_最小顶点集)

POJ 3692-Kindergarten(二分图_最小顶点集)

2024-11-04 12:01:39   209人阅读

Kindergarten
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 5477 Accepted: 2653

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

题意：有G个女孩，B个男孩，M条询问，女孩之间相互认识，男孩之间相互认识，女孩和男孩之间有m条相互关系。老师想从男孩女孩之间找出最多的人做游戏，这些人要求相互之间都认识。

思路：又是一种新的建图方式。 男孩之间相互认识，女孩之间相互认识，男孩女孩之间有的相互认识有的不认识，要向找出最多的相互认识的人来做游戏，显然用二分图最大匹配是行不通的，同组的人不能有关系，要想同组的人相互之间不能有关系，而且和另一个组扯上关系，只能是从不认识的下手，试想总人数中减去相互不认识的最少人数不就是相互认识的最大人数么？所以图就出来了。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
using namespace std;
int map[1010][1010];
int vis[1010];
int link[1010];
int G,B;
int dfs(int u)
{
    int i;
    for(i=1;i<=B;i++){
        if(!vis[i]&&map[u][i]){
            vis[i]=1;
            if(link[i]==-1||dfs(link[i])){
                link[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int m;
    int i,j;
    int cnt=0;
    int sum;
    int a,b;
    while(~scanf("%d %d %d",&G,&B,&m)){
        cnt++;
        sum=0;
        memset(link,-1,sizeof(link));
        if(G==0&&B==0&&m==0)
            break;
        for(i=1;i<=G;i++)
            for(j=1;j<=B;j++)
            map[i][j]=1;
        while(m--){
            scanf("%d %d",&a,&b);
            map[a][b]=0;
        }
        for(i=1;i<=G;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))
             sum++;
        }
        //printf("%d---->",sum);
       printf("Case %d: %d\n",cnt,G+B-sum);

    }
    return 0;
}


POJ 3692-Kindergarten(二分图_最小顶点集)


联系
我们