# Ollivanders: Makers of Fine Wands since 382 BC.

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 935    Accepted Submission(s): 523

Problem Description

Input

There are several cases. For each case, there is two integers N and M in the first line,which mean there is N wizards and M wands(0 < N <= M <= 100). Then M lines contain the choices of each wand.The first integer in i+1th line is Ki,and after these there are Ki integers Bi,j which are the wizards who fit that wand. (0<=Ki<=N,1<=Bi,j<=N)

Output

Only one integer,shows how many wands Ollivander can sell.

Sample Input

3 4 3 1 2 3 1 1 1 1 0

Sample Output

2

Hint

Hint

Wand 1 fits everyone, Wand 2,3 only fit the first wizard,and Wand 4 does not fit anyone.So Ollivanders can sell two wands: sell Wand 1 to Wizard 2 and Wand 2 to Wizard 1,or sell Wand 1 to Wizard 3 and Wand 3 to Wizard 1 ,or some other cases. But he cannot sell 3 wands because no 3 wands just fit 3 wizards.

Source

``` 1 #include<cstring>
2 #include<cstdio>
3 #include<cstdlib>
4 using namespace std;
5 int const maxn=102;
6 int n,m;
7 bool mat[maxn][maxn];
8 bool vis[maxn];
9 int mac[maxn];
10 bool match(int x)
11 {
12     for(int i=1;i<=n;i++)
13     {
14         if(mat[x][i]&&!vis[i]){
15             vis[i]=1;
16             if(!mac[i]||match(mac[i])){
17                 mac[i]=x;
18                 return 1;
19             }
20         }
21     }
22     return 0;
23 }
24 int main(){
25     int a,b;
26     //freopen("test.in","r",stdin);
27     while(scanf("%d%d",&n,&m)!=EOF){
28        memset(mat,0,sizeof(mat));
29        memset(mac,0,sizeof(mac));
30        for(int i=1;i<=m;i++){
31          scanf("%d",&a);
32         while(a--){
33          scanf("%d",&b);
34          mat[i][b]=1;
35         }
36     }
37
38     int ans=0;
39     for(int i=1;i<=m;i++){
40       memset(vis,0,sizeof(vis));
41       if(match(i))ans++;
42     }
43     printf("%d\n",ans);
44  }
45   return 0;
46 }```

0 条评论

• ### uva-----11292 The Dragon of Loowater

Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

• ### HDUOJ ------1398

http://acm.hdu.edu.cn/showproblem.php?pid=1398 Square Coins Time Limit: 2000/100...

• ### cf(#div1 B. Dreamoon and Sets)(数论)

B. Dreamoon and Sets time limit per test 1 second memory limit per test 256 ...

• ### 机器学习神书推荐 Hands on Machine Learning

本次为大家推荐的是一本机器学习神书英文原版《Hands-On Machine Learning with Scikit-Learn and TensorFlow...

• ### 微软被勒索诈骗勒索的软件网络

该公司周一宣布，与世界各地的电信供应商一道，能够切断Trickbot僵尸网络使用的基础设施，使其不再被用来引发新的感染或激活已经植入计算机系统的勒索软件。

• ### Satpy基础系列教程(3)-Satpy总览

Satpy is designed to provide easy access to common operations for processing met...

• ### EQUS-帮助查看公式（CS SE）

可视化通常是简化信息和帮助人们理解复杂数据的一种方式。在本文中，我们描述了电子表格公式（EQUS）交互式可视化的设计，开发和评估。这项工作是合理的，理由是这些工...

• ### 七步理解深度学习

原文链接请点击阅读原文。 There are many deep learning resources freely available online,but...

• ### 【双语频道】ONOS架构原理

The purpose of this ONOS talk is to convey the rationale behind our approach to ...

• ### 通过音乐驱动的机器人情感韵律和手势，建立人机信任（Human-Computer Interaction）

随着人机协作机会的不断扩大，信任对于机器人的充分参与和利用变得越来越重要。建立在情感关系和人际关系纽带上的情感信任尤其重要，因为它对错误更有弹性，并增加了合作的...