题目描述(ID:12407)
标题: 关押的冗兵
标签: 图结构 二分图 二分图匹配
详情:
戎兵入侵了啊哈编程星球,啊哈沃德为了拯救星球,英勇战斗,俘虏了一批戎兵,现把男女戎兵犯人分开管理。编程星球的开发人员开发出了一款产品:阿尔法监视器。该监视器能对特定的一对男女戎兵进行监视,以避免他们在监狱中进行破坏。现在已经生产出了一批阿尔法监视器,为了节约监视器,我们需要使用尽可能少的阿尔法监视器来监视戎兵。
输入格式:
输入的第一行是三个正整数n(1<=n<=200),m(1<=m<=200),l(1<=l<=2000),用空格隔开,表示男戎兵和女戎兵的数量和这一批阿尔法监视器的数量,男戎兵 女戎兵编号分别从1~n 1~m。
接下来l行,每行输入两个正整数x y,用空格隔开,表示其中一个阿尔法监视器可以监视的男戎兵和女戎兵的编号。
输出格式:
输出一个数,表示最少阿尔法监视器的个数。
样例:

输入

5 5 11
1 2
1 5
2 2
2 3
2 4
3 1
3 5
4 1
4 2
4 5
5 2

输出

6
登录并解答