【题意】：Jamie有一个电话簿，给出这n个人可以归属的组别，她需要把电话簿上的n个人分成m组。现在让你确定一种合理的方案使得该方案中人数最多的那个组别的人数最小。
【题解】：又是一个最大值最小化的问题，自然我们又想到二分枚举+网络流判定这样的做法，这题还可以用二分图多重匹配来做，但是我不会。这题构图很明显，加入源点s向每个联系人连边，容量为1，表示每个人只能分到一个组里面去。如果联系人i能够分到组j里面，连边i->j，容量为1。再加入一个汇点t，每个组都向t连边，容量为组的可容纳人数。最后只需要二分组的可容纳人数，判断最大流是否等于n即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 const int inf = 1 << 30;
6 #define maxn 1600
7 #define maxm 1000000
8 int n, m, s, t;
9 int eh[maxn], pre[maxn], cur[maxn], tot, low[maxn], cnt[maxn], dist[maxn];
10
11 struct Edge {
12 int u, v, cap, flow, next;
13 }et[maxm];
14
15 struct person {
16 int cnt, st[550];
17 void init() {
18 cnt = 0;
19 }
20 }person[1100];
21
22 void init() {
23 tot = 0;
24 memset(eh, -1, sizeof(eh));
25 }
26
27 void add(int u, int v, int cap, int flow) {
28 Edge e = {u, v, cap, flow, eh[u]};
29 et[tot] = e;
30 eh[u] = tot++;
31 }
32
33 void addedge(int u, int v, int cap) {
34 add(u, v, cap, 0), add(v, u, 0, 0);
35 }
36
37 int isap(int s, int t, int n) {
38 int u, v, now, flow = 0;
39 memset(cnt, 0, sizeof(cnt));
40 memset(dist, 0, sizeof(dist));
41 memset(low, 0, sizeof(low));
42 for(u = 0; u <= n; u++) cur[u] = eh[u];
43 low[s] = inf, cnt[0] = n;
44 u = s;
45 while(dist[s] < n) {
46 for(now = cur[u]; now != -1; now = et[now].next)
47 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
48 if(now != -1) {
49 cur[u] = pre[v] = now;
50 low[v] = min(low[u], et[now].cap - et[now].flow);
51 u = v;
52 if(u == t) {
53 for(; u != s; u = et[pre[u]].u) {
54 et[pre[u]].flow += low[t];
55 et[pre[u]^1].flow -= low[t];
56 }
57 flow += low[t], low[s] = inf;
58 }
59 } else {
60 if(--cnt[dist[u]] == 0) break;
61 dist[u] = n, cur[u] = eh[u];
62 for(now = eh[u]; now != -1; now = et[now].next)
63 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
64 dist[u] = dist[et[now].v] + 1;
65 cnt[dist[u]]++;
66 if(u != s) u = et[pre[u]].u;
67 }
68 }
69 return flow;
70 }
71
72 bool build(int cap) {
73 init();
74 s = 0, t = n + m + 1;
75 for(int i = 1; i <= n; i++) {
76 addedge(s, i, 1);
77 for(int j = 0; j < person[i].cnt; j++)
78 addedge(i, person[i].st[j] + n + 1, 1);
79 }
80 for(int i = 1; i <= m; i++) addedge(i + n, t, cap);
81 return isap(s, t, t - s + 1) == n;
82 }
83
84 int solve() {
85 int l = 1, r = n, res = -1;
86 while(l <= r) {
87 int mid = (l + r) >> 1;
88 if(build(mid)) res = mid, r = mid - 1;
89 else l = mid + 1;
90 }
91 return res;
92 }
93
94 int main() {
95 char ch, name[20];
96 while(~scanf("%d%d", &n, &m)) {
97 if(!n && !m) break;
98 for(int i = 1; i <= n; i++) {
99 scanf("%s", name);
100 person[i].init();
101 ch = getchar();
102 while(ch != '\n') {
103 scanf("%d", &person[i].st[person[i].cnt++]);
104 ch = getchar();
105 }
106 }
107 int ans = solve();
108 printf("%d\n", ans);
109 }
110 return 0;
111 }