HDU 1669 Jamie's Contact Groups（多重匹配+二分枚举）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1669

题目大意：

给你各个人可以属于的组，把这些人分组，使这些组中人数最多的组人数最少，并输出这个人数。
解题思路：

一组可以有多人，一人只能分到一组，显然是多重匹配，只要枚举一下每组的限制人数limit，用多重匹配判断即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int N=1e3+;

const int M=5e2+;

int n,m,limit;

int link[M][N];

bool vis[M];

vector<int>v[N];

bool dfs(int u){

    for(int i=;i<v[u].size();i++){

        int t=v[u][i];

        if(vis[t]) continue;

        vis[t]=true;

        if(link[t][]<limit){

            link[t][++link[t][]]=u;

            return true;

        }

        for(int i=;i<=limit;i++){

            if(dfs(link[t][i])){

                link[t][i]=u;

                return true;

            }

        }

    }

    return false;

}

//多重匹配

bool mul_match(){

    for(int i=;i<=m;i++) link[i][]=;

    for(int i=;i<n;i++){

        memset(vis,false,sizeof(vis));

        if(!dfs(i)) return false;

    }

    return true;

}

int main(){

    while(~scanf("%d%d",&n,&m)&&n&&m){

        for(int i=;i<=n;i++) v[i].clear();

        char op[];

        for(int i=;i<n;i++){

            scanf("%s",op);

            int x;

            while(getchar()==' '){

                scanf("%d",&x);

                v[i].push_back(x);

            }

        }

        //二分枚举上限人数

        int l=,r=1e3,ans=;

        while(l<=r){

            limit=(l+r)/;

            if(mul_match()){

                r=limit-;

                ans=limit;

            }

            else l=limit+;

        }

        printf("%d\n",ans);

    }

    return ;

}