Jamie's Contact Groups HDU - 1669 二分+二分图多重匹配

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int N = 1000+10;
const int M = 500+10;
int n,m;
int map[N][M],vlink[M],link[M][N],max_cap;
bool vis[M];
int path(int s) {
    for(int i=0; i<m; i++) {
        if(map[s][i] && !vis[i]) {
            vis[i]=true;
            //当前组的人数 ，如果当前组已经超过最大人数 
            if(vlink[i]<max_cap) {
                link[i][vlink[i]++]=s;
                return 1;
            }
            //遍历其他组 
            for(int j=0; j<vlink[i]; j++) {
                if(path(link[i][j])) {
                    link[i][j]=s;
                    return 1;
                }
            }
        }
    }
    return 0;
}
bool solve(int mid) {
    max_cap=mid;
    memset(vlink,0,sizeof(vlink));
    for(int i=0; i<n; i++) {
        memset(vis,false,sizeof(vis));
        if(!path(i))
            return false;
    }
    return true;
}
int main() {
    char str[20],c;
    int a;
    while(scanf("%d %d",&n,&m)==2 && (n||m)) {
        memset(map,false,sizeof(map));
        for(int i=0; i<n; i++) {
            scanf("%s",str);
            while(true) {
                scanf("%d%c",&a,&c);
                map[i][a]=true;
                if(c=='\n') break;
            }
        }
        int l=1,r=n,ans=n;
        while(l<=r) {
            //取中点 
            int mid=(l+r)>>1;
            //如果能取到 
            if(solve(mid)) {
                //如果当前值小于答案 
                if(mid<ans)
                    //更新答案 
                    ans=mid;
                //去递归 
                r=mid-1;
            } else 
                l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Jamie's Contact Groups HDU - 1669 二分+二分图多重匹配

原文：https://www.cnblogs.com/QingyuYYYYY/p/12432804.html