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

题目链接：点击查看

题目大意：给出n个联系人，以及m个分组，现在需要将n个联系人分到m个分组中，需要满足让人数最多的组的人数最少，输出这个值

题目分析：因为是让最大值最小，所以肯定是要用二分解决，因为分组对于人来说是一对多，显然可以让人去找分组，也就是二分图的多重匹配，我们直接用最大流来解决就好了，每次二分答案，根据答案设置流量，若满流增大答案，否则减小答案

代码：

#include<iostream>
#include<cstdio> 
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const int N=2e3+100;
 
struct Edge
{
	int to,w,next;
}edge[N*N];//边数
 
int head[N],cnt,n,m;

bool maze[1010][510];
 
void addedge(int u,int v,int w)
{
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	edge[cnt].to=u;
	edge[cnt].w=0;//反向边边权设置为0
	edge[cnt].next=head[v];
	head[v]=cnt++;
}
 
int d[N],now[N];//深度 当前弧优化
 
bool bfs(int s,int t)//寻找增广路
{
	memset(d,0,sizeof(d));
	queue<int>q;
	q.push(s);
	now[s]=head[s];
	d[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(d[v])
				continue;
			if(!w)
				continue;
			d[v]=d[u]+1;
			now[v]=head[v];
			q.push(v);
			if(v==t)
				return true;
		}
	}
	return false;
}
 
int dinic(int x,int t,int flow)//更新答案
{
	if(x==t)
		return flow;
	int rest=flow,i;
	for(i=now[x];i!=-1&&rest;i=edge[i].next)
	{
		int v=edge[i].to;
		int w=edge[i].w;
		if(w&&d[v]==d[x]+1)
		{
			int k=dinic(v,t,min(rest,w));
			if(!k)
				d[v]=0;
			edge[i].w-=k;
			edge[i^1].w+=k;
			rest-=k;
		}
	}
	now[x]=i;
	return flow-rest;
}
 
void init()
{
    memset(now,0,sizeof(now));
	memset(head,-1,sizeof(head));
	cnt=0;
}
 
int solve(int st,int ed)
{
	int ans=0,flow;
	while(bfs(st,ed))
		while(flow=dinic(st,ed,inf))
			ans+=flow;
	return ans;
}

bool check(int x)
{
	init();
	int st=N-1,ed=st-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(maze[i][j])
				addedge(i,j+n,1);
	for(int i=1;i<=n;i++)
		addedge(st,i,1);
	for(int i=1;i<=m;i++)
		addedge(i+n,ed,x);
	return solve(st,ed)==n;
}

int main()
{
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF&&n+m)
	{
		memset(maze,false,sizeof(maze));
		for(int u=1;u<=n;u++)
		{
			char s[20];
			scanf("%s",s);
			int v;
			while(scanf("%d",&v))
			{
				maze[u][v+1]=true;
				if(getchar()=='\n')
					break;
			}
		}
		int l=0,r=inf,ans;
		while(l<=r)
		{
			int mid=l+r>>1;
			if(check(mid))
			{
				ans=mid;
				r=mid-1;
			}
			else
				l=mid+1;
		}
		printf("%d\n",ans);
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}