1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #include<cstdio> 6 using namespace std; 7 8 const int maxn = 100; 9 const int INF = 0x3f3f3f3f; 10 int cap[maxn][maxn]; 11 int flow[maxn][maxn]; 12 int s,t; 13 int n,m; 14 int num[30]; 15 int ansf; 16 17 void EK(){ 18 ansf = 0; 19 memset(flow,0,sizeof(flow)); 20 int res[maxn]; 21 bool vis[maxn]; 22 int p[maxn]; 23 memset(p,0,sizeof(p)); 24 queue<int> Q; 25 while(true){ 26 memset(vis,0,sizeof(vis)); 27 memset(res,0,sizeof(res)); 28 Q.push(s); res[s] = INF; p[s] = s; vis[s] = true; 29 30 while(!Q.empty()){ 31 int u = Q.front(); Q.pop(); 32 for(int v=0;v<=n+m;v++){ 33 if(!vis[v] && cap[u][v] > flow[u][v]){ 34 vis[v] = true; 35 p[v] = u; 36 Q.push(v); 37 res[v] = min(res[u],cap[u][v] - flow[u][v]); //printf("%d %d %d \n",u,v,res[v]); 38 } 39 } 40 } 41 if(res[t] == 0) break; 42 ansf += res[t]; 43 for(int i=t;i!=s;i=p[i]){ 44 flow[p[i]][i] += res[t]; 45 flow[i][p[i]] -= res[t]; 46 } 47 } 48 return; 49 } 50 51 int main() 52 { 53 //if(freopen("input.txt","r",stdin)== NULL) printf("Error\n"); 54 int T; 55 cin>>T; 56 for(int cas=1;cas<=T;cas++){ 57 cin>>n>>m; 58 memset(cap,0,sizeof(cap)); 59 s = 0; t = n + m; 60 int k; 61 cin>>k; 62 memset(num,0,sizeof(num)); 63 for(int i=1;i<=k;i++){ 64 int a; 65 cin>>a; 66 num[a]++; 67 } 68 for(int i=1;i<=m;i++){ 69 if(num[i]) cap[s][i] = num[i]; 70 } 71 for(int i=m+1;i<m+n;i++){ 72 cin>>k; 73 memset(num,0,sizeof(num)); 74 for(int j=1;j<=k;j++){ 75 int a; 76 cin>>a; 77 num[a]++; 78 } 79 for(int j=1;j<=m;j++){ 80 if(num[j]>1) cap[i][j] = num[j] - 1; 81 else if(!num[j]) cap[j][i] = 1; 82 } 83 } 84 for(int i=1;i<=m;i++){ 85 cap[i][t] = 1; 86 } 87 EK(); 88 printf("Case #%d: %d\n",cas,ansf); 89 } 90 }