无汇源上下界可行流的模板题。 说是模板题，其实想让它除了二分以外加点变化也是有点困难的。 关于上下界网络流的问题，以前偷懒没学，本来打算这几天补上，加上今天薛昊这个催化剂又来问我，于是就今天开始补了。 在这里我非常非常非常非常非常推荐这篇博文 总结的非常详细，写的有十分通俗易懂，全文十分连贯，评论也有人说看完给人一种荡气回肠的感觉。 当我看完无汇源上下界可行流的时候，我马上敲了一蛤这道题，就一 A 了。妙啊！ 下面简单说一下无汇源上下界可行流的解法，不详细说明，具体请看上面的链接。 无汇源上下界可行流可用建图+最大流解决，建图方式如下： * 对每个给定的边建边，容量为 up – down * 记录每个点的 down 流量差，这里设 入流量为正，出流量为负。如果总的流量差大于0，建边 src -> 该点，容量为流量差。否则，建边 该点 -> des 容量为流量差的负值。 没了，再跑一遍最大流，如果能满流就说明有可行流，…
LCA 好题！ 这道题我暂时只知道用Tarjan的解法。 Tarjan解法完美地运用了Tarjan的核心原理与性质： 深度优先搜索时的向下局部性。自己乱取得，蛤蛤蛤 题意： 给你一棵树，每个节点有一个权值。给你很多个询问，每个询问两个点。要你在给定点的树链上找到有序的最大差值。 思路： 首先考虑分治。设树链 u -> lca -> v 答案无非只有三种情况： 1. u -> lca 的最大差值 2. lca -> v 的最大差值 3. lca -> v 的最大值 – u -> lca 的最小值 考虑dp维护这四个值。 因为运用Tarjan算法的时候，基于dfs，在你的眼里，当前节点就是向下整棵树的根节点，你完全不会去考虑往上的节点。 所以你现在使用的四个值，刚好是你当前节点的孩子节点的最优值。 基于这个事实，…
K短路裸题。 这里的K短路是基于每个点只能访问一次，也就是说这个K短路必须是一条链。 再换句话说，这个K短路的K是有限制的，如果超过了这个限制，就输出 -1 。 这是和之前多校的次短路不一样的地方。 简单说一下K短路的解决思路： 首先我们应该认识到，最最简单的最短路算法是基于 bfs 改进而来，我们用 bfs 的思路继续拓展，在第一次到达终点后并不停止，而是继续 bfs 搜索，直到第K次到达终点，就是我们要求的答案。 当然，单纯的 bfs 是瞎 jb 搜，堆优化的spfa效率良好，但我们可以更进一步优化。 K短路于此之上还用了 A* 优化，先对反图 最短路遍历一遍，在正图遍历的时候，除了对起点 src 到当前距离 堆优化以外，还对当前距离进行答案估计，并将其优先级先于距离。 仔细想一想，其实很显然，不过为什么最短路不用 A* 优化呢？ 因为有处理估值函数的时间，最短路都已经求完了。…
淦啊……我之前自以为入门的最大团DP优化板子是错的，我说怎么和极大团计数差别这么多，那个原先的根本就是一个被谁自创的dfs+dp优化算法，速度平均慢一倍！！！
说句别的，终于刷完这套……给出链接
最大团与稳定婚姻专题
题意：
要你找出一个数量不小于 k 的最大团，使得最大团中的最短距离最大。
思路：
二分距离+最大团判定
老实说我一开始没想到，但看到这个思路之后就是豁然开朗，感觉二分的思路都是这样的……
然后疯狂TLE……不知道为什么，查了一下，最大团板子太慢了……原来学得是民间算法！！
AC Code
#include
最大团问题之极大团计数。 啊呀啊呀，基本都会是板子题啦…… 但是尽管是板子题，上次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
稳定婚姻的判定问题。 老实说，写了几题后发现稳定婚姻问题几乎都是板子题……囧…… 而且我作为入门题写的那道题好歹还披了一件外套，有几道完完全全的裸题写得我是非常的空虚…… 回到这道题，这道题应该算是稳定婚姻判定的裸题了。 假如我们再次无脑套模板，复杂度还是在( O(n^2) )左右。 我们从另一个角度来考虑。如果我可以找到一个相互出轨的夫妻，那就是不稳定的。 从而，对于一个已知的婚姻匹配，如果存在一对夫妻离婚，但不会对其他夫妻造成任何影响，那么这组婚姻匹配就是稳定的。 稳定婚姻的判定就是通过这种方式找到可以相互出轨的夫妻。 一个可行解法就是求强联通分量。对于已知匹配建立好单向二分图，对于可出轨匹配用反向边表示。然后求一下强联通分量。如果存在一组匹配，他们被染色的数量超过 ( 1 ) 是什么颜色呢？？ 那这个婚姻匹配就是不稳定的。 复杂度为Tarjan的复杂度，估计在( O( n ) ) 左右。 题意： 先给你一组婚姻匹配，再给你几组可出轨匹配，问你对于每一对夫妻，他们的匹配是否安全。 思路： 裸题啦，裸题，看了我上面的陈述就知道该怎么写了。 A…