codves 2776 寻找代表元 && 51nod 2006 飞行员配对(二分图最大匹配)

codves 2776 寻找代表元

时间限制: 1 s

空间限制: 256000 KB

题目描述 Description

广州二中苏元实验学校一共有n个社团，分别用1到n编号。
广州二中苏元实验学校一共有m个人，分别用1到m编号。每个人可以参加一个或多个社团，也可以不参加任何社团。
每个社团都需要选一个代表。谦哥希望更多的人能够成为代表。

输入描述 Input Description

第一行输入两个数n和m。
以下n行每行若干个数，这些数都是不超过m的正整数。其中第i行的数表示社团i的全部成员。每行用一个0结束。

输出描述 Output Description

输出最多的能够成为代表的人数。

样例输入 Sample Input

4 4
1 2 0
1 2 0
1 2 0
1 2 3 4 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

各个测试点1s

数据范围
n,m<=200

#include<cstdio>
#include<cstring>
const int N=210;
int map[N][N];
int book[N];
int tag[N];
int n,m;
bool find(int x)
{
    for(int i=1;i<=m;i++)
    {
        if(map[x][i]&&(!book[i]))
        {
            book[i]=1;
            if(!tag[i]||find(tag[i]))
            {
                tag[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    
    scanf("%d %d",&n,&m);
    int p;
    for(int i=1;i<=n;i++)
    {        
        while(true)
        {
            scanf("%d",&p);
            if(!p) break;
            else map[i][p]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(book,0,sizeof(book));
        if(find(i)) ans++;
    }
    printf("%d",ans);
    return 0;
}

View Code

(xixi)匈牙利算法;

http://blog.csdn.net/dark_scope/article/details/8880547

-------------

类似的题：2006 飞行员配对(二分图最大匹配)

解：同上，（一开始看错了题目），“No Solution!”即为ans==0的情况；

======================