《欧拉回路，拓扑，2-SAT》.pptxVIP

欧拉回路，拓扑，2-SAT;欧拉回路;有向欧拉图;存在欧拉路的条件;有向图: ? 图连通，所有点出度=入度，或者有一个点入度-出度=1，有一个点出度-入度=1。同样，当所有点出度=入度时任意点可作为起点；而后者必须以出度-入度=1的点做起点，入度-出度=1的点做终点。 ;存在欧拉回路的条件;混合图（扩展不讲）: ? 构造网络流模型来进行判断，具体如下: ?? ? ? ? ?先对原图中的无向边随便定向，然后计算每个点的出度和入度，如果存在|出度-入度|为奇数的点，则不存在欧拉回路(因为欧拉回路要求每个点出度=入度，而对无向图随便定向不影响点的 |出度-入度| 的奇偶性，所以如果存在这样的点，不论怎么样都不可能找到欧拉回路)；否则，对于每个点来说，求出它的|出度-入度|/2，得到X。 构造网络： 原图中的无向边怎么定向，网络中就怎么连边，容量为1；然后对于每个点,如果(出度-入度)大于0，就和源点连边，容量为X；如果(出度-入度)小于0，就和汇点连边，容量为X；然后对这个网络求最大流，如果能够满流，则原图存在欧拉回路，否则不存 在。 ;?? HDU3018 Ant? Trip? 给定一个无向图G，问最少需要几笔画完。 ?? ?POJ1386 Play on words 给定N个单词，问是否能否按照规定排成一排，两个单词iff有相同端点才可以挨着。如acm，go，micolog，就可以按照acm-micolog-go排成一列。 ????? ??? HDU2894 DeBruijin??? DeBruijin图问题，给定一个数N，求一个长为2^N的01串，使得任意N个子串表示0到2^N-1所有的数恰好一次，且要求字典序最小。 ??? POJ2230 Watchcow?? 给定一个无向图，保证存在欧拉路，找到一条欧拉路，输出点的访问顺序。 ?? ? 。 ;POJ1041 John’s trip?? 给定一个有向图，如果存在欧拉路的话输出边的访问顺序。 ???????POJ2337 Catenyms? 和POJ1386一样的题意，但是要求把最后的结果输出且要求字典序最小。 ?????? POJ1392 Ouroboros Snake 和HDU2894几乎一样的题目，给出N个K，找出长度为N时串的第K个数。 ?????POJ1637 Sightseeing tour? （选做） 混合图的欧拉回路，判断是否存在，按上面提到的方法构造网络判断满流即可;哈密顿回路（NP问题）;经典NP完全问题尚未发现多项式算法;Hamilton路(选看);欧拉路Hamilton路;拓扑排序;拓扑排序;拓扑排序;拓扑排序;DAG Toj-1762 Tetris Alphabet Toj-1195 Sorting It All Out ;2-SAT;2-SAT;2-SAT;建图的基本原则是：对两个必须在一起的变量连边。即：如果选了A必须选B，那么连A到B的边。2-SAT的问题一般是二维变量，我们且称每一个二元组为{A,~A},几个常用的模型为： ??????? (1) u 和 v 不能同时选择: u-~v,??? v-~u； ???????????? (因为选了u必须选~v，选了 v 必须选~u) ??????? (2) u 和 v 至少选择一个: 转化为不能同时选择~u和~v，参见(1) ??????? (3) 必须选择u:? ~u-u ;????????一类是判断可行性问题，还有一类是构造可行解问题。 对于第一类，构图完成后对图求SCC，然后如果有一组变量u和~u属于同一个SCC，那么无解，否则有解，题目一般喜欢二分+判断可行。 ; 第二类问题是找出一组可行解，较复杂 证明参考上面提到的第二篇文章，可以这样构造：对原图求完SCC后，将图进行缩点操作，形成一个新的有向无环图(DAG) G,然后对G的逆图G‘进行拓扑排序然后红蓝染色，具体做法是在排序的过程中，对于没有染过色的点u染红色，这里u是缩点后的图中的点，然后对和u矛盾的点染蓝色(和u矛盾的点就是属于强连通分量u中的点uu的矛盾点~uu所属的强连通分量v，有点绕口~~)，其实就是说对于原图的点uu，求完SCC后属于强连通分量u，而uu的矛盾点~uu属于强连通分量v，那么如果u染了红色，则给v染蓝色(终于说清楚了)。这样一直操作到结束。然后对于原图中的每个点u，如果点u所属的强连通分量染了红色，那么u即为可行解中的一个解。;POJ-2723: 题目大意：有N对钥匙和M道门，每对钥匙只能使用其中一把，即使用其中一把后另外一把就消失了。每道门有两个锁孔，打开任意一个锁孔就能开门，现在问最后能开多少道