最大团问题之极大团计数。 啊呀啊呀，基本都会是板子题啦…… 但是尽管是板子题，上次ccpc网络赛卡我的题，我当时要是有个最大团的板子，就可以直接过了…… 极大团计数和最大团不大一样，这里有wiki上的伪代码 BronKerbosch(All, Some, None): if Some and None are both empty: report All as a maximal clique //所有点已选完，且没有不能选的点,累加答案 for each vertex v in Some: //枚举Some中的每一个元素 BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v)) //将v加入All，显然只有与v为朋友的人才能作为备选，None中也只有与v为朋友的才会对接下来造成影响 Some := Some…
好烦，感觉自己的图论知识都有了，但是一旦写起来还是非常欠缺…… 什么时候我才能踩完所有的坑，成就大佬之路呢…… 今天多校的第二道签到题…… 是的，签到题……但是我没有写出来为什么呢……我也想知道为什么我老是会这样那样的地方写错…… 今天错的地方是没有去重，还像条疯狗一样跑去BC官方博客理论了…… 在这里先道个歉…… 但是题解的确没写清楚 题意： 给你一个有向图，有环，无重边，无自环。 问你是否存在两个不联通的点。 思路： 拿到题的第一思路，拓扑排序，有环就缩点呗！ 然后开始疯狂WA…… 思路没错，但是在缩点后没有去重，导致缩点后一条边的出度增加，拓扑排序失败…… 好烦……讲道理缩点+拓扑，虽然简单，但也没有沦落到这种比赛的签到题上…… 原因就是数据很小，允许 ( O ( n^2 ) )解题…… 可能因为图论学傻了，没想到也不愿意用暴力做…… 暴力的方法是，枚举每一个点，记录它可以达到的点，构成一个二维矩阵，然后遍历一下矩阵，看是否存在相互不可达的点即可。 虽然暴力在我眼里有点不齿，但是优雅的暴力还是非常值得认可的。…
听了Yasola瞎逼逼打算去搞一下那些很混乱的东西。
首先就是这个最大团问题
建议先点开看看上面的百度百科链接。虽然东西很多，我也只是浏览了一下
瞎逼逼与个人理解
首先必须强调的是最大团是一个NP-Hard问题，目前并没有一个合适的在多项式时间内完美求得正解的算法。
而Bron–Kerbosch算法，名字好像是非常吊，其实就是各种优化过的搜索算法。
学习博客点这里
简单说一下个人理解。
Bron–Kerbosch算法基于基本搜索，但优化之处很多，优化有如下
1. 比较常见的指定顺序搜索，避免重复
2. 对于当前深度 dep , 如果剩余点数与之相加都不能更新 ans ，就剪枝
3. dp 优化，用dp记录之前搜索得到的最大团数量，如无法更新ans，剪枝。
下面有两个入门 板子 题
HDU 1530 Maximum Clique
题意：
最大团的裸题。给你邻接矩阵，让你求最大团的点数。
思路：
套一套模板就行啦……
AC Code
#include
由已知婚姻匹配求出所有可出轨匹配。
因为稳定婚姻问题中的匹配都是完美匹配，因此也可以换一种说法，已知一个完美匹配，求出所有完美匹配。
这道题或许可能是我这辈子做的最后一道稳定婚姻问题……因为本来出的就少，感觉都是套路……
求稳定婚姻就是模拟的板子，判定和所有出轨匹配就是tarjan缩点……
尽管如此，但还是不得不学啊……
题意：
一个国王有很多个儿子，这些儿子有很多个喜欢的女孩。国王把这些女孩都找了过来，刚好儿子和女孩的数量相同。所以只能一夫一妻了。
国王要大臣给个可行方案，大臣给了。国王又要所有可行方案。大臣就烧脑子了。
儿子最多2000个……囧……厉害厉害
思路：
其实方法的话……基本还是和稳定婚姻的判定是一样的。稳定婚姻判定点这里
在求出所有强联通分量之后，找出男性的所有可婚配配偶 和 与他在同一个强联通分量的女性的交集。
从小到大输出这个交集就是我们要求的答案。
AC Code ( 时间略长……
#include
稳定婚姻的判定问题。 老实说，写了几题后发现稳定婚姻问题几乎都是板子题……囧…… 而且我作为入门题写的那道题好歹还披了一件外套，有几道完完全全的裸题写得我是非常的空虚…… 回到这道题，这道题应该算是稳定婚姻判定的裸题了。 假如我们再次无脑套模板，复杂度还是在( O(n^2) )左右。 我们从另一个角度来考虑。如果我可以找到一个相互出轨的夫妻，那就是不稳定的。 从而，对于一个已知的婚姻匹配，如果存在一对夫妻离婚，但不会对其他夫妻造成任何影响，那么这组婚姻匹配就是稳定的。 稳定婚姻的判定就是通过这种方式找到可以相互出轨的夫妻。 一个可行解法就是求强联通分量。对于已知匹配建立好单向二分图，对于可出轨匹配用反向边表示。然后求一下强联通分量。如果存在一组匹配，他们被染色的数量超过 ( 1 ) 是什么颜色呢？？ 那这个婚姻匹配就是不稳定的。 复杂度为Tarjan的复杂度，估计在( O( n ) ) 左右。 题意： 先给你一组婚姻匹配，再给你几组可出轨匹配，问你对于每一对夫妻，他们的匹配是否安全。 思路： 裸题啦，裸题，看了我上面的陈述就知道该怎么写了。 A…
第一次看了理论之后自己敲代码直接 1A ！！！蛤蛤蛤蛤！！！ 嗝～～ 稳定婚姻问题的定义与求解方法详见百度百科 中文维基上写的比较简单。 简单说一下个人理解与解法。个人感觉还是挺有趣的。 稳定婚姻问题是构建在男女双方的二分图基础上的。如果对于现有的一个男女匹配，存在一个男人 a 比起现在的妻子女人 a 更喜欢 女人 b 。而与此同时，女人 b 比起现在的丈夫男人 b ，更喜欢男人 a 。那么男人 a 与 女人 b 很可能会出轨。我们称这个婚姻匹配是不稳定的。 反之，如果不存在这个会出轨的男女匹配，则称这个婚姻匹配是稳定的。 稳定婚姻问题的求法在上面的中文维基上有伪代码，我也基本上按照这个理论敲的。 略为详细的步骤如下： 1. 为每一个男性与女性确定一个各自的异性在自己眼里的排名。但是记录方式不太一样，根据我的写法，男性需要记录的是排名第几是那个女性，女性需要记录的是这个男性排第几。 2. 将每个男性加入队列。尝试为每个男性按排名配偶，如果这个女性暂时没有配偶，那么暂时进行匹配。否则，与她现在的配偶进行比较。…
01分数规划之最优比例生成树……
这道题，好坑……
一开始WA了，然后找了一个博客，WA，照着敲，WA，再照着敲，WA，索性复制再改，WA，最后复制粘贴，他的也WA了。md
感觉我写题的时候很容易石乐志，然后就很难过题……
好几场比赛都验证了……
题意：
给你一张图上的所有点，由所有点得出每条边的两个权值，欧式距离与高度差。
要你和找出一个生成树，使得 高度差的和比上欧式距离和最小。
思路：
最优比例生成树的经典题。其实只要掌握了01分数规划的思想，你就照着prime敲就好了。
我这里用了迭代法，感觉迭代法更套路一些……而且速度比较快。
#include
分数划分之最优比例环。 分数划分中比较常见的限制之一，在图中筛选的必须是一个环。 本来在入门题的时候对于以下转换公式有考虑过这样的一个问题： $ \sum \left( \left( a_{i}-L\times b_{i}\right) \times x_{i}\right) $ 为什么只需要考虑 ( \left( a_{i}-L\times b_{i}\right) ) 与 ( 0 ) 之间的关系，而不用去管( x_i )了呢？明明取舍( x_i )也是对答案会造成影响的。 而实际上，举个例子，对于最优比例环来说，成不成环就是一个主要的筛选的过程。然后再是对于二分的值( L )，如果对于当前( L) 仍有可提升空间。若仍有提升空间，就说明( L)…