专题十 匹配问题 POJ 2289 Jamie‘s Contact Groups（二分答案+二分图多重匹配）

POJ 2289 Jamie’s Contact Groups

题意：

有一个通讯录，
要求

1. 你把每个好友分组。有m个组 $[0,m)$
2. 每个好友的所能去的组有限制。
3. 使得每个好友都能分到一个组。
4. 求 $min(所有组中largest的人数)$

思路：

1. 最小值中的最大值。（很裸的二分）
2. 之后匹配，就是二分图多重匹配。

反思：

1. sstream的初始化。

	stringstream ss;ss.str("");

AC

#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdio>
#define mst(x,a) memset(x,a,sizeof(x))
#define fzhead EDGE(int _to,int _next)
#define fzbody to(_to), next(_next)
using namespace std;
const int maxm=5e5+10;
const int maxn=1e3+10;
struct EDGE{int to,next;EDGE(){}fzhead:fzbody{}
}e[maxm];
struct node{int cnt,k[maxn],mx;
}link[510];
int head[maxn],vis[510];
bool used[510];
int n,m,cnt,mx;
void add(int bg, int to){e[cnt]=EDGE(to,head[bg]);head[bg]=cnt++;
}
void init(){getchar();mst(head,-1);mx=cnt=0;string line,name;int v,tot=0;for(int i=1; i<=n; i++){//while(getline(cin,line)){getline(cin,line);stringstream ss(line);//init ss.str("");ss>>name;tot=0;while(ss>>v)add(i,v),tot++;mx=max(mx,tot);}
}
bool dfs(int u){for(int i=head[u]; i!=-1; i=e[i].next){int v=e[i].to;if(!used[v]){used[v]=1;if(link[v].cnt<link[v].mx){//if(!vis[v]||dfs(vis[v])){link[v].k[link[v].cnt++]=u; //vis[v]=u;return 1;}//return 1;for(int j=0; j<link[v].cnt; j++)//}if(dfs(link[v].k[j])){link[v].k[j]=u;return 1;}}}return 0;
}
bool check(int x){mst(vis,0);mst(link,0);for(int i=0; i<m; i++)link[i].mx=x;int ans=0;for(int i=1; i<=n; i++){mst(used,0);ans+=dfs(i);}return ans==n;
}
void sol(){int ans=0,l,r;l=1;r=n;while(l<=r){int mid=(l+r)>>1;// cout<<l<<' '<<r<<endl;// cout<<mid<<endl;if(check(mid))ans=mid,r=mid-1;else l=mid+1;}printf("%d\n",ans);
}
int main()
{while(scanf("%d%d", &n, &m)&&(n||m)){init();sol();}return 0;
}