本文主要是介绍pku 2989,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
极大团问题:
我还是写一下思路吧:
这个就是个记忆搜索。一开始考虑问题规模为一个节点,这样的极大团是一。再考虑第二个点。这就有以下几种情况了。
1.这个点和前面没这个点的问题中的某个极大团可以融合成一个新的极大团,这样子,极大团个数不会增加。
2.要是这个点和前面的某个极大团不完全融合,那就找到它和那个极大团能融合的部分,这样肯定得到的是个完全子图,但是不是极大就不一定了。这要判断一下。遍历之前的点,看看有没有不在此团中但是可以融合进去的,有的话,这个团我们就不要了。后面肯定会有个更大的给你。为什么呢?假设当问题规模为i+1时,含点V(i+1)的极大团S,那么当问题为i规模时,是不是一定有个极大团为S-V(i+1),这是显然的。我把一些操作写进了struct f_int里,应该没什么别的了。
主要是这个集合他不好表示。本来应该用hash的,但是比较麻烦,我也没写过,就用了map,集合用啥呢?用四个int就可以了,128位,代表128个数字。集合的交就是&,查找就是位移和1与一下看是不是0.
800多ms。。。
标程代码:
70多ms。。。
这篇关于pku 2989的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!