POJ2289-Jamie's Contact Groups(二分+多重匹配)

题目链接:POJ2289-Jamie's Contact Groups

题意:

n个人,m个社交团体,一个人可能对应多个社交团体,但只能参加一个社交团体,问所有社交团体中人数最多的团体最少有多少人。

题解:

二分多重匹配,先二分答案,即每个团体的容量,然后进行匹配,若每个人都能成功匹配,那么该容量就是可行的。

参考代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int n, m;
bool used[2009];
int match[2009][2009], CNT[2009];
int edge[2009][2009];
bool dfs(int u, int MaxCap)
{
    for (int v = 0; v < m; v++)
    {
        if (edge[u][v] && !used[v])
        {
            used[v] = 1;
            if (CNT[v] < MaxCap)
            {
                CNT[v]++;
                match[v][CNT[v]] = u;
                return 1;
            }
            for (int j = 1; j <= CNT[v]; j++)
            {
                if (dfs(match[v][j], MaxCap))
                {
                    match[v][j] = u;
                    return 1;
                }
            }
        }
    }
    return 0;
}
bool MaxMatch(int MaxCap)
{
    memset(CNT, 0, sizeof(CNT));
    for (int i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(used));
        if (!dfs(i, MaxCap))
            return 0;
    }
    return 1;
}
int main()
{
    while ((scanf("%d%d", &n, &m)) && (n || m))
    {
        memset(edge, 0, sizeof(edge));
        for (int i = 1; i <= n; i++)
        {
            int v;
            char str[20], c;
            scanf("%s", str);
            while (1)
            {
                scanf("%d%c", &v, &c);
                edge[i][v] = 1;
                if (c == '\n')
                    break;
            }
        }
        int l = 1, r = n + 1, ans = n;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (MaxMatch(mid))
            {
                r = mid;
                ans = mid;
            }
            else
                l = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。