`
hunxiejun
  • 浏览: 1137533 次
文章分类
社区版块
存档分类
最新评论

NYoj 239 二分图最大匹配

 
阅读更多

话说这道题是一道最最基本的二分图最大匹配,,,稍微了解二分图的acmer应该都能1A的,,悲剧的是。。我纠结啊,,,纠结啊,,纠结了好久。。。。昨天下午做了一道大连赛区现场赛的一道题,剩下的时间就是做这道题了,本来用邻接矩阵做的这道题,,,意料之中的TLE了,,今天早上来了用邻接表做,,,一直有错误,,就这样,,赵错找了2个小时,,,最后终于ac了。。。。留下做个模板,题目:

月老的难题

时间限制:1000ms | 内存限制:65535KB
难度:4
描述

月老准备给n个女孩与n个男孩牵红线,成就一对对美好的姻缘。

现在,由于一些原因,部分男孩与女孩可能结成幸福的一家,部分可能不会结成幸福的家庭。

现在已知哪些男孩与哪些女孩如果结婚的话,可以结成幸福的家庭,月老准备促成尽可能多的幸福家庭,请你帮他找出最多可能促成的幸福家庭数量吧。

假设男孩们分别编号为1~n,女孩们也分别编号为1~n。

输入
第一行是一个整数T,表示测试数据的组数(1<=T<=400)
每组测试数据的第一行有两个整数n,K,其中男孩的人数与女孩的人数都是n。(n<=500,K<=10 000)
随后的K行,每行有两个整数i,j表示第i个男孩与第j个女孩有可能结成幸福的家庭。(1<=i,j<=n)
输出
对每组测试数据,输出最多可能促成的幸福家庭数量
样例输入
1
3 4
1 1
1 3
2 2
3 2
样例输出
2
ac代码:



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics