「POJ-2289」Jamie's Contact Groups (二分图多重匹配+二分)

发表于 | 分类于 ，

「POJ-2289」amie’s Contact Groups
二分图最大多重匹配，求最大分组的最小值

题意

给定一系列联系人和其可分到的组，对联系人分组，在所有联系人都有分组的情况下，使最大分组的值最小。求最大分组的最小值。

解法

匈牙利算法，求解可容纳量$limit$内的二分图多重匹配。二分答案，求出最小的满足左侧点全部匹配的$limit$值即为所求解。也可用网络流求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=1000+5;//左边最大点数
const int maxm=500+5;//右边最大点数
int graph[maxn][maxm],vis[maxm];//图G和增广路访问标记
int match[maxm][maxn];//左边元素与右边元素第n次匹配
int nx,ny,m;//左边点数，右边点数,边数
int limit;
int cnt[maxm];//右边点已匹配值

bool find_path(int u)//找增广路
{
    for(int i=0; i<ny; i++)//注意，这里节点是从0开始编号，题目有时是从1开始编号
    {
        if(graph[u][i] && !vis[i])//不在增广路
        {
            vis[i]=1;//放进增广路
            if(cnt[i]<limit)//如果当前已匹配数量小于可容纳量，则直接匹配
            {
                match[i][cnt[i]++]=u;
                return true;
            }
            for(int j=0; j<cnt[i]; j++)
            {
                if(find_path(match[i][j]))//如果先前已匹配右边的点能另外找到增广路，则此点仍可匹配
                {
                    match[i][j]=u;
                    return true;
                }
            }
        }
    }
    return false;
}

int max_match()//计算多重匹配的最大匹配数
{
    int res=0;
    memset(match,-1,sizeof(match));
    memset(cnt,0,sizeof(cnt));
    for(int i=0; i<nx; i++)
    {
        memset(vis,0,sizeof(vis));
        if(find_path(i)) res++;
    }
    return res;
}

bool all_match()//判断左边的点是否都与右边的点匹配了
{
    memset(cnt,0,sizeof(cnt));
    for(int i=0; i<nx; i++)
    {
        memset(vis,0,sizeof(vis));
        if(!find_path(i)) return false;
    }
    return true;
}

int main()
{
    char s[20],c;
    int u;
    while(scanf("%d%d",&nx,&ny)!=EOF&&(nx||ny))
    {
        memset(graph,0,sizeof graph);
        for(int i=0;i<nx;i++)
        {
            scanf("%s",s);
            for(;;)
            {
                scanf("%d%c",&u,&c);
                graph[i][u]=1;
                if(c=='\n') break;
            }
        }
        int l=1,r=nx,ans=0x3f3f3f3f;
        while(r>l)
        {
            limit=(l+r)/2;
            max_match();
            if(all_match()) r=limit;
            else l=limit+1;
        }
        printf("%d\n",r);
    }
    return 0;
}