【題意】：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 }