请编写程序,实现求解无权二部图最大匹配的匈牙利算法。
输入格式:
输入首先在第一行给出 3 个正整数,依次为二部图 G=(U∪V,E) 中 U 点集顶点数、V 点集顶点数(均不超过 100)和边数 m。
随后 m 行,每行给出一条连接 U 点集顶点和 V 点集顶点的边,格式为 u v
,其中 u
属于 U,v
属于 V。两个点集的顶点编号均从 0 开始。同行数字间以一个空格分隔。
输出格式:
在一行中输出 最大匹配值 = x
,其中 x
为最大匹配数。
输入样例:
4 3 7
0 0
0 1
1 1
1 2
2 0
2 1
3 2
输出样例:
最大匹配值 = 3