衡阳网站seo,兼职设计师在哪里接活,wordpress 全局字段,安阳门户网站总的感受: 这里大概囊括了一下图论的基础知识#xff0c;图论是一个比较考验思维的部分。 尤其是后面有关二分图,网络流等的分支,对建模转化的要求还是很高的。 进入正题了#xff1a; 一、最短路#xff1a; 这一个部分不想多讲#xff0c;虽然是很基础的一个部分#xf…总的感受: 这里大概囊括了一下图论的基础知识图论是一个比较考验思维的部分。 尤其是后面有关二分图,网络流等的分支,对建模转化的要求还是很高的。 进入正题了 一、最短路 这一个部分不想多讲虽然是很基础的一个部分但是也很重要。 题目 1、Telephone Lines。p.s:二分答案最短路。 2、Roads and Planes。p.s:Topo序dijkstra。 3、Cow Relays。p.s:Floyd矩阵乘法。 三连击 二、最小生成树 基础算法的话也不多讲了。主要是其实有些这种类型的题也很考验思维。。。 题目 1、picnic planning。 p.s:最小生成树枚举。 三、树的直径与LCA 树的直径求法 ① 树形DP。 ②两遍BFS/DFS。 LCA的求法 ①树上倍增。 ②Tarjan并查集离线。 这一类型的题目一般需要能够发现隐藏在题目中的一些优秀的性质然后和这些东西挂上联系然后就很舒服了(有前提的略略略)。 题目 1、APIO2010巡逻 p.s:分类讨论树的直径。 题解传送门 2、NOIP2007树网的核 p.s:分析性质树的直径。 题解传送门 3、POJ3417Network p.s:问题转化树上差分。 题解传送门 4、SDOI2015寻宝游戏 p.s:dfs序set虚树??!!题解传送门 5、严格次小生成树 p.s:最小生成树树上倍增。题解传送门 6、NOIP2012疫情控制 p.s:二分答案贪心树上倍增。题解传送门 四、基环树 一般用来作为树问题的扩展。。解决基环树问题常用思路一般先考虑树然后挂上一条边后产生的影响和没说一样。。。 1、IOI2008Island p.s:基环树直径。题解传送门 五、负环与差分约束系统 负环的判定spfa不多聊。 讲下差分约束系统 这是一种特殊的N元不等式组它的N个变量a1...aN满足一些形如下的约束 ai-ajbkaiajai-ajbk... 然后需要解决的问题就是求一组解使得上述约束全部满足。 可以发现上述的式子和最短路需要满足的三角形不等式dis[y]dis[x]ver(x,y)十分相似。 那么我们可以考虑到把这些约束看作是两两变量之间的边相对应的跑最短长路即可。 具体一点 对于形如:ai-ajck的式子我们可以转换成aiajck。 那么就相当于向j往i连了一条长为ck的边那么对应的跑最短路即可。特殊的如果存在负环无解 而对于形如:ai-ajck的式子就转换成aiajck,可以发现只需将最短路改成最长路即可。 题目 咕咕咕。。。 六、Tarjan与图的连通性 无向图桥割边判定: low[y]dfn[x]; 无向图割点判定 low[y]dfn[x];
//需要注意的是需要判断根节点的特殊情况... 无向图边双连通分量e-DCC求法 把所有的桥去掉后得到的所有的连通块都是一个e-DCC。 无向图点双连通分量v-DCC求法 把所有的割点去掉后得到的所有的连通块都是一个v-DCC。 并不是。。。一定不能乱来啊233 事实上可以发现一个割点可能出现在多个v-DCC中。 这个时候就按照割点判断法则来把用一个栈维护起来的点一个个弹出他们组成一个v-DCC。同时需要把割点的标记清空因为后续它还有可能出现在别的v-DCC中。 e-DCC的缩点比较常规需要注意的是v-DCC的缩点新的图应该包括了每一个v-DCC和每一个割点。 有向图强连通分量SCC的求法对于每一个点若存在 low[x]dfn[x]; 那么把栈中维护的元素弹到x为止。 SCC的缩点也比较常规。 有向图的必经点和必经边。 注意此处不考虑有环的情况。对于有环的情况请自行了解支配树。 既然没有环可以直接正反两次进行Topo排序。 记录到x路径条数,不妨设从S到x路径条数为f[x]从x到T路径条数为t[x]。 ① 如果对于一条有向边x,y。如果满足 f[x]*t[y]f[T]; 则此边为必经边。 ② 如果对一个点x。如果满足 f[x]*t[x]f[T]; 则此点为必经点。 题目 1、POI2008BLO p.s:割点。题解传送门 2、Knights of the Round Table p.s:点双连通分量奇环。题解传送门 七、2-SAT问题 对于N个变量每个变量只有两种取值。然后有M个条件每个条件是关于两个变量取值的限制。 问能否找到一组合法的赋值方案使得M个条件都满足。 判定是否合法的方法 首先对这N个点建一张2N个点的图i和iN对应的点i的两个取值。 然后根据每一个条件连有向边一般需要转一下思维。 最后tarjan缩强连通分量如果任意一个SCC内存在iiN那么就不合法。否则合法。 求一组合法赋值方案的方法 这是个人理解由于选择一个零出度点不会对其他点造成影响。 所以 1、我们可以建反图Topo序相当于在原图自底向上进行Topo。 每遇到一个没有确定赋值的点就给它和它对应的点赋值。 2、由于我们发现tarjan缩点得到的每一个SCC的顺序正好是自底向上的所以我们可以直接赋值。 val[i]c[i]c[opp[i]];//c是强连通分量编号...//i代表xi,0,opp[i]代表xi,1... 八、二分图和网络流 定义一张没有奇环的无向图是二分图。 二分图判定方法dfs染色。若存在相邻两个点他们的颜色相同那么就存在奇环。 最大匹配求法① 匈牙利算法 ② 网络流。 完备匹配一张图具有完备匹配当且仅当两边的点都为N个且最大匹配为N。 多重匹配在最大匹配的基础上点可以连不超过一特定限制数量的另一侧的点。 最大带权匹配边有边权在最大匹配的前提下使权值和最大。 最大带权匹配求法① KM算法 ② 费用流。 需要注意的是KM算法仅仅适用于二分图具有完备匹配所以一般都是费用流。 二分图最小点覆盖等于最大匹配数。 简略证明一下 首先由于每条匹配边都肯定需要至少取一个端点所以不可能小于最大匹配数。因此只需要给出一组构造使得点数等于最大匹配数即可。构造如下首先先求出二分图最大匹配。然后对于每一个左部非匹配点在进行一次寻找增广路的过程必然失败同时进行访问标记。最后选出左部未访问的节点和右部访问了的节点这些点构成一组点数为最大匹配数的最小点覆盖。原因左部的非匹配点显然都被标记了右部的非匹配点肯定没被标记一对匹配点要么同时被标记要么同时没被标记。那么1、匹配边都被覆盖了因为恰好每条匹配边只取了一个点。2、两个端点都是非匹配点的情况不存在与最大匹配矛盾。3、左部是非匹配点右侧是匹配点的非匹配边被覆盖了。4、右部是非匹配点左侧是匹配点的非匹配边左部点一定没被访问所以也被覆盖了。 证毕。 二分图最大独立集等于总点数-最小覆盖即也等于总点数-最大匹配。 证略。 网络流初步 最大流EK算法dinic算法当前弧优化。 最小割最小割等于最大流。 费用流spfa-EK费用流。 题目 1、Ants p.s:二分图带权最小匹配。题解传送门 2、网络流24题 No p.s...题解传送门 最后的最后 蒟蒻的图论部分就到此结束了有些地方讲的有点含糊不清请多包容。 上述题解会很快跟上的。。。希望别咕掉了ο The Real End 转载于:https://www.cnblogs.com/Bhllx/p/10610275.html
