二分+二分图多重匹配。
/* 1669 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = ;
const int maxm = ;
bool M[maxn][maxm];
bool visit[maxm];
int can[maxm][maxm];
int sz[maxm];
int n, gn, bound; bool dfs(int u) {
rep(i, , gn) {
if (M[u][i] && !visit[i]) {
visit[i] = true;
if (sz[i] < bound) {
can[i][sz[i]++] = u;
return true;
}
rep(j, , sz[i]) {
if (dfs(can[i][j])) {
can[i][j] = u;
return true;
}
}
}
} return false;
} bool judge(int bound_) {
bound = bound_;
memset(sz, , sizeof(sz));
rep(i, , n) {
memset(visit, false, sizeof(visit));
if (!dfs(i))
return false;
} return true;
} void solve() {
int l, r, mid;
int ans; l = ;
ans = r = n;
while (l <= r) {
mid = (l + r) >> ;
if (judge(mid)) {
ans = mid;
r = mid - ;
} else {
l = mid + ;
}
} printf("%d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif char name[];
int gid;
char ch; while (scanf("%d %d", &n, &gn)!=EOF && (n||gn)) {
memset(M, false, sizeof(M));
rep(i, , n) {
scanf("%s", name);
while () {
scanf("%d%c", &gid, &ch);
M[i][gid] = true;
if (ch == '\n')
break;
}
}
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
二分+网络流Dinic也可以解。
/* 1669 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct {
int v, c, nxt;
} Edge_t; const int INF = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
const int maxv = maxn + maxm;
const int maxe = maxn*maxm*+;
Edge_t E[maxe];
int F[maxe];
int head[maxv], head_[maxv];
int id[maxm];
int dis[maxv], Q[maxv];
int m;
int n, gn;
int s, t; void init() {
memset(head, -, sizeof(head));
m = ;
s = ;
t = n + gn + ;
} void addEdge(int u, int v, int c) {
E[m].v = v;
E[m].c = c;
E[m].nxt = head[u];
head[u] = m++; E[m].v = u;
E[m].c = ;
E[m].nxt = head[v];
head[v] = m++;
} bool bfs() {
int l = , r = ;
int u, v, k; Q[r++] = s;
memset(dis, , sizeof(dis));
dis[s] = ; while (l < r) {
u = Q[l++];
for (k=head[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (!dis[v] && E[k].c>F[k]) {
dis[v] = dis[u] + ;
if (v == t)
return false;
Q[r++] = v;
}
}
} return true;
} int dfs(int u, int val) {
if (u==t || val==)
return val; int ret = ;
int tmp, v; for (int& k=head_[u]; k!=-; k=E[k].nxt) {
v = E[k].v;
if (dis[v]==dis[u]+ && E[k].c>F[k] && (tmp=dfs(v, min(val, E[k].c-F[k])))>) {
F[k] += tmp;
F[k^] -= tmp;
ret += tmp;
val -= tmp;
if (val == )
break;
}
} return ret;
} int Dinic() {
int ret = , tmp; while () {
if (bfs())
break; memcpy(head_, head, sizeof(head));
while () {
tmp = dfs(s, INF);
if (tmp == )
break;
ret += tmp;
}
}
#ifndef ONLINE_JUDGE
printf("Dinic = %d\n", ret);
#endif
return ret;
} bool judge(int bound) {
rep(i, , gn+)
E[id[i]].c = bound;
memset(F, , sizeof(F)); return Dinic()>=n;
} void solve() {
int l = , r = n, mid;
int ans = -; while (r >= l) {
mid = (l + r) >> ;
if (judge(mid)) {
ans = mid;
r = mid - ;
} else {
l = mid + ;
}
} printf("%d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif char name[];
char ch;
int gid; while (scanf("%d %d", &n, &gn)!=EOF && (n||gn)) {
init();
rep(i, , n+) {
scanf("%s", name);
while () {
scanf("%d%c", &gid, &ch);
addEdge(i, gid+n+, );
if (ch == '\n')
break;
}
}
rep(i, , n+)
addEdge(s, i, );
rep(i, , gn+) {
id[i] = m;
addEdge(n+i, t, );
}
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}