首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

HDU 1068 Girls and Boys 二分图 最大独力集 字符串

2012-06-27 
HDU 1068 Girls and Boys 二分图 最大独立集 字符串独立集是指两两之间没有边的顶点集合。顶点数目最多的集

HDU 1068 Girls and Boys 二分图 最大独立集 字符串

独立集是指两两之间没有边的顶点集合。顶点数目最多的集合称为最大独立集。

二分图最大独立集 = 顶点数 -  二分图最大匹配。

 

所以这题在于解决二个问题:

1、求二分图的最大匹配。

由于左右两个集合是同一集合,不分男女。所以,理论上讲存在0到3,就一定存在3到0。刚开始的想法是只将0到3记起来,

3到0就不记录了。这样在求最大匹配是可以少点计算。可是却WA了!不解。我还是觉得这种思路没错,并且可以减少时间。

个人怀疑是数据的问题了。

2、输入的每组数据可以看成是一个字符串。然后在处理之。当然,这题不看成字符串也是可以的。因为数组数据的“:”、

“()”的位置是固定的,那么就可以一个一个数来输入了。

 

AC代码:2871MS


 

 

 

 

热点排行