最近网络流有点写累了，就尝试着写了一下二分图。
这是我第一道二分图多重匹配的题目，基本上是看着模板敲的……
因为中间在main函数内外都定义了n,m ，搞得我debug了好久……
二分图多重匹配想比喻二分图单匹配来说，只是多加了几步，本质上还是一样的。基本上看代码就能看懂。
题意：
有个女神的备胎很多，每次找备胎都很麻烦，搞得她很困扰。现在女神想把他的备胎们分成m组，根据关系有的必须放在特别的组，但是女神数学不好，于是女神随手找了个备胎帮助计算，在满足条件的情况下有个组内人数max，现在要你求最小的max。
思路：
二分人数+多重匹配。
最大流也可。二分到汇点的容量即可。
这里有个小麻烦，就是有不定数量的数字。
一般人会立马想到，最麻烦的getchar() , 好一点的想到 stringstream
这里比较合适的应该是 一起输入一个数字和字符，如果字符是换行符号则退出。
AC Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define fill(ary, num) memset((ary), (num), sizeof((ary)))
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int n, m, maxcap;
bool vis[maxn], g[maxn][maxn];
int link[maxn][maxn], vlink[maxn];
char buf[60];
bool dfs(int u)
{
each(i, m) if (g[u][i] && !vis[i])
{
vis[i] = true;
if (vlink[i] < maxcap) {
link[i][vlink[i]++] = u;
return true;
}
each(j, vlink[i]) if (dfs(link[i][j]))
{
link[i][j] = u;
return true;
}
}
return false;
}
bool hungary(int mid)
{
maxcap = mid;
fill(vlink, 0);
each(i, n)
{
fill(vis, false);
if (!dfs(i))
return false;
}
return true;
}
inline void input(int u)
{
int a;
char c;
scanf("%s", buf);
while (true) {
scanf("%d%c", &a, &c);
g[u][a] = true;
if (c == '\n')
break;
}
}
int main()
{
ios::sync_with_stdio(false);
while (scanf("%d %d", &n, &m) != EOF && (n || m)) {
fill(g, false);
each(i, n) input(i);
int l = 1, r = n, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (hungary(mid))
r = mid - 1;
else
l = mid + 1;
}
printf("%d\n", r + 1);
}
return 0;
}