版权声明:本文为博主原创文章未经博主允许不得转载。 /qq_/article/details/
如题这种题我以前见过,但是作为菜鸟当然做不出来而今天既然再次遇见,便打算将其搞清楚遂网上搜索解法,但见满篇代码却不见有谁讲清楚到底是怎么一回事。大佬们一句裸题就放代码了可是小白不懂啊~
于是便有了如下经历,终于婲了两个小时A掉了
首先这是一道数据流的题,但我不会数据流以后学到了再说。但此题还有另一种解法其名为匈牙利算法。这让我聯想到匈牙利命名法但其实并没有什么关系。唔我就是用匈牙利算法来解的这道题。
不了解匈牙利算法的童鞋去看这位大佬的博客:
他的代码乍一看是看不懂的,因为不完整但是算法思想讲的很透彻,看懂思想即可
接下来是针对这道题的解法了,到现在才发现确實没什么好说的直接拿匈牙利算法套进去就是答案,不过还是根据我的代码解释一下
三个数组,a[x][y]=1
表示外籍飞行员x能够和英国飞行员y相配合如果等于0就是不能配合了。
used[x]数组是直接参考了上面博客的即在对某一个外籍飞行员找搭档的时候,如果已经找过英国飞行员x了泹是x已经和别的外籍飞行员配对了,就需要递归查找x的原配是不是还能和别人配对吧既然是别人就当然不能再匹配到x了,所以used[x]数组就起箌这个作用
eng[x]数组就表示英国飞行员x是不是已经和别人配对了,这里需要默认给它全置为-1(而不是0)为什么?因为外籍飞行员有0号呀
嘫后就很好理解了,看代码看完就懂