POJ 3692 Kindergarten（最大匹配+匈牙利算法+补图思想）

青旅半醒 2022-06-10 04:12 128阅读 0赞

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

题解：

题意：

有n个女生，m个男生，q对数据，

每一对数据表示女生x认识男生y，老师要做一个游戏要求所有人都认识，让你求最大可以挑选的人数

思路：

意识到了是二分图匹配，可是数据转化成图的思想依旧很弱，还有就是这类题反向思维很重要，这里求的是最大可以挑选的互相认识的人，那么我们是不是能用最少的人覆盖掉最多互相不认识的情况，即是求图的补图，最小顶点覆盖，然后用总人数减去互相都不认识的人的人数得到的就是最大的互相认识的人了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    using namespace std;
    int p[205][205];
    int used[205];
    int vis[205];
    int n,m;
    int find(int u)//匈牙利算法
    {
        int i;
        for(i=1;i<=m;i++)
        {
            if(!vis[i]&&p[u][i])
            {
                vis[i]=1;
                if(!used[i]||find(used[i]))
                {
                    used[i]=u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        int i,j,k,q,cas=1,x,y;
        while(scanf("%d%d%d",&n,&m,&q)!=EOF)
        {
            if(m==0&&n==0&&q==0)
                break;
            for(i=1;i<=n;i++)//初始化全为1
            {
                for(j=1;j<=m;j++)
                {
                    p[i][j]=1;
                }
            }
            memset(used,0,sizeof(used));
            for(i=0;i<q;i++)
            {
                scanf("%d%d",&x,&y);
                p[x][y]=0;//表示认识
            }
            int ans=0;
            for(i=1;i<=n;i++)//匹配用最少的人覆盖掉最多不认识的情况
            {
                memset(vis,0,sizeof(vis));
                if(find(i))
                    ans++;
            }
            printf("Case %d: %d\n",cas,n+m-ans);//总人数减去互相不认识的人就是答案
            cas++;
        }
        return 0;
    }