6.11集训队选拔赛有道欧拉图的题，没带模板就尝试去写没写出来。因为在acm里欧拉图的题可以说是少之又少，就算是我现在想要去复习一编，然而连题目都找不到几个。就算有欧拉图的题目，也只是考察他的性质（欧拉图的判定啊什么的）
阅读之前请读者自备图论相关常识
Fleury算法是一种解决欧拉图的常见算法，它的核心思想在于我在进欧拉路径的时候，尽量去走非桥边。其实这是很显然的，因为当你在走过了一个桥边，原图将被分为两个子图，如果之前还有边未走完，那么我将无法回到原子图上，也就无法形成欧拉路径了。
优先走非桥边，这是一个非常必要的前提条件，而事实证明，这也是一个充分条件。
以下是我整理的个人模板
#include
11.HDU 1814 Peaceful Commission
题意：
建图老题意，表示有n对人要出席一个会议，但是有m个恶劣的关系不允许同时出现。
但是不一样的地方就是需要输出可行解的最小序列
思路：
让你判断一下还是很简单的，但是输出最小序列真的让博主感到很无力，想了很长时间也没有一个快速的方法。看了题解是说暴搜索可解，我这里說一下暴搜思路。
先将所有节点染成白色（初始化），再进行遍历。如果已经染成红色或者黑色的节点就跳过，否则，我们先尝试将第一个节点染成红色，再进行暴力dfs缩点，暴力过程中，优先让第一个节点染成红色，第二个染成黑色。如果没有任何冲突，则表示缩点成功。否则尝试将第二个节点染成红色，再缩点，如果还不行，就说明无解了。
#include
6. POJ 2296 Map Labeler 题意： 平面区域内部有n个点，以这个点为上底边中心或者下底边中心作正方形，要求使所有正方形都不相交，问正方形最大的边长为多少。 思路： 和炸弹那道题差不多，二分区间，判断即可。 令( Dis_x [a][b] = \left| x[a] – x[b] \right| , Dis_y [a][b] = \left| y[a] – y[b] \right| )，边长为 mid，设 a 表示 a 矩阵放上面，~a 表示 a 矩阵放下面。 建图： * (Dis_x[a]…
传送门
昨天第一次跟两个妹子一起打……真特么那个紧张啊 人生赢家请闭嘴
这题应该是属于我的题目但到最后还是没有A掉的，如果到了现场赛，这样怕是要打铁了……
题意：
给你n个点与其权值，求一棵生成树，满足 A/B 的值最大
其中，A = 生成树中任选的一条边所连接的两个点的权值和，B = 生成树总长 – 你选中的边的长度
思路：
为满足 A/B 最大，则必须使得 A 尽量大 ，B 尽量小。
假设选中的边已经确定，那么剩下的 n-2 条边肯定在最小生成树中(这是显然的）。那么，其实我们可以先生成一棵最小生成树，然后枚举他的边，将它暂时删除。
在一棵树中删除一条边，将形成两棵子树（这里把点也考虑上），为使重新构成生成树，我们必须在两棵子树之间重新构造一条边。为使 A 最大，我们只要两棵子树上分别寻在权值最大的点即可。
#include
附带我的学习来源，这里包含以上所有题目的题解和代码。实在想不出来我就是看这里的。
1. HDU 3062 Party
题意：
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？ （中文题面就复制粘贴一下了……）
思路：
非常典型的 2-sat 模型，如果两对夫妻 A B ，丈夫A0 与 妻子B1 有仇，那么就建 A0 -> B0 , A1 -> B1 两条边。
#include
本文起始请听我先说一句 ***的HDU4429!!!!!!!!! 这道题是我想自己写个LCA专题的起因。你要是去google题解的话全是用暴力求得。不知道为什么，你写题写到后面你会发现题解的代码全特么一个样子。说明他们很可能是不太懂，然后从某一个博客中看了代码，照样子写了，然后A了就得过且过的样子。当然我是不喜欢这样的。然后我就想用下tarjan求LCA，顺便复习一下算法。 结果！！！！ WA了两天！！！！ 忍无可忍交了一发暴力，60ms 秒过！！！！！玛德，这题绝对有问题！！！！我现在就要开个专题先验证一下我自己的算法。 先是放一下我对这题的题解 HDU 4429 Split the Rectangle 附带本人评价：狗屎 好题 题意： 给你一个矩形，再给你一些边，这些边用来分割矩形。 再是几次询问，每次询问给你两个点，要求你每次删去几条边，使得这两个点在同一个矩形中，问此时剩下的矩形数最多还有多少。 思路： 每次分割矩形后，使所形成的两个小矩形成文被分割矩形的两个孩子。如此这般就会形成一棵二叉树。 每次查询求出两个点所在的叶子节点，再…
tarjan算法的第三个应用 求强连通分量 强连通分量我就不具体介绍了 这次的关键数组含义仍然没变 low[u] 仍然还是 u 能到达的最小的 low[v] ( low[v] 又由它最小的 low[v’] 决定 这里有个很关键的点 low[u] == dfn[u] 若以 求割点与桥的tarjan理解 表示 u 的子树的结点中最早能返回到 u，不能访问到u的祖先， 而 u 又必然能访问到 其子树，因此很简容易便能理解 u 及其子树形成了一个最大的连通块 即 强连通分量 而根据 dfs 的 递归与回溯特性 我们以一个栈来存储一个强连通分量 当得到 low[u]==dfn[u] 时可以逐个出栈得到强连通中的所有结点 鉴于强连通的特性…
前天打周赛做到 HDU4738 绞尽脑汁都没想到用什么好的方法来解决这个问题 周赛结束之后跟Yasola和xcy讨论了一下居然用到 tarjan算法 exm？？？ tarjan不是用来求 lca的么？？？ 回去怒补了一发才知道 tarjan原来是一系列是算法 根据我看到的博客原文 可以这么说 tarjan是个天才 他伟大的一生创造了无数的算法 统称 tarjan算法 其中有三个最有名的 求lca 求图的割点与桥 （还有一个啥来着 反正我最近一定要学一下 无奈看完之后就断电熄灯了 一直拖到昨晚才学 基本概念： 图论里的桥 即 连接两个子图唯一边 如果这条边被你砍了 整个图将被你一分为二 图论里的割点 同桥的理解 只是对象是一个结点 如果这个结点被你分开 那么整个图也将分裂 因为我也是刚学 hdu4738 的对象也是一张无向图 以下均以无向图进行讨论 有向图日后再说 在tarjan算法中 对于一张图 我以深搜为核心 并且每个节点只访问一次 那么最后深搜得到的图 会是什么？？ 是一棵树！！ （这真是太奇妙了 我自认为对搜索有点信心 但是从来没有想过这样的应用…