题目描述(ID:12404)
标题: 完美的牛栏(混合编号)
标签: 图结构 二分图 二分图匹配
详情: 农夫约翰上个星期刚刚建好了他的新牛棚,他使用了最新的挤奶技术。不幸的是,由于工程问题,每个牛栏都不一样。第一个星期,农夫约翰随便地让奶牛们进入牛栏,但是问题很快地显露出来:每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期,农夫约翰刚刚收集到了奶牛们的爱好的信息(每头奶牛喜欢在哪些牛栏产奶)。一个牛栏只能容纳一头奶牛,当然,一头奶牛只能在一个牛栏中产奶。
给出奶牛们的爱好的信息,计算最大分配方案。
输入格式:
第一行 两个整数,N (0 <= N <= 400) 和 M (0 <= M <= 2000) 。N 是农夫约翰的奶牛数量和新牛棚的牛栏数量之和,M表示一共有M条奶牛和牛栏的对应关系。

第二行到第M+1行 一共 M 行,每行对应一个奶牛和牛栏的对应关系。第一个数字 a 表明奶牛的编号。第二个数字 b 表示奶牛a愿意产奶的牛栏的编号
输出格式:
只有一行。输出一个整数,表示最多能分配到的牛栏的数量。
样例:

输入

10 11
1 4
1 7
2 4
2 5
2 6
8 3
8 7
9 3
9 4
9 7
10 4

输出

4
登录并解答