坑爹啊！！！！！！！当时这道题想了我好久好久 想到各种歪的地方 到最后没有一个地方是想对的 都是想多的 日
怎么说呢 一眼看出是欧拉图问题 但是一开始没想起 异或运算的规则 傻傻的把欧拉路径的算法给敲了一直超时
//顺便稍微写一下异或运算的性质好了 1. 两个相同的数异或得 0 2.0与任意一个数异或 则这个数不变 3. 多个数异或与顺序无关
回归正题 关于欧拉图的性质 简单回顾一下
欧拉通路 所有结点连通并且只有两个结点的 度 为奇数
欧拉回路 所有结点连通并且所有结点的 度 为偶数
另外 欧拉通路的起点和终点固定 欧拉回路的起点（也是终点）任意
这样就可以写了 比完之后关注了一下这道题的博客 感觉他们还是有些逻辑漏洞 然而他们还是A了
AC code
#include
应该是很明显的差分约束的题目了 只要想清楚 节点的含义 路径的含义 建好模 就好说 这里我直接设 d[I] 表示 第i个事件的开始时间 根据题意 可得 FAS：d[u]+val[u]>=d[v] FAF：d[u]+val[u]>=d[v]+val[v] SAF：d[u]>=d[v]+val[v] SAS：d[u]>=d[v] 题目要求最小值，需要转化为： d[u]–d[v]>=-val[u] d[…
这是一道多米诺骨牌的题目 从第一块骨牌出发 问最后一块倒下的骨牌在哪 若是端点 直接输出时间和端点 否则输出时间和 最后的骨牌在哪两块之间
怎么说呢 直接用spfa 算出 从1节点到其他节点的单源最短路径 找出最大的
因为作为最短路的最大值 它必定是一条路径 就算有其他的路径到达这个节点 那也是肯定逼这条最短路径要慢的
所以我们从这个最大节点出发 除了最短路径的其他路径都会是没有走过的路径（也就是还能继续走下去
详见注释
AC Code
#include
LCA 即 最近公共祖先
对于一棵有根树，就会有父亲结点，祖先结点。
0
|
1
/ \
2 3
/ \
4 5
举几个例子 如图 这棵树的所有节点的根节点都是 0
但是
4 5 的LCA 是3
2 5的LCA 是1
1 3的LCA 是1
这里要介绍的 求最近公共祖先的算法是 Tarjan 算法 算法的核心思想在于 我们从一棵树的根节点开始向下深搜 当我们回溯的时候 我们才把两个集合合并 并更新根节点
这就意味着 对于一个节点 我们只有访问过他的所有子节点和他本身之后才更新他的根节点 我再简单点说 这样操作就实现了从叶子节点不断向上更新根节点 如果我们再更新之前完成记录LCA的操作 一切并迎刃而解
附上伪代码
…//parent为并查集，FIND为并查集的查找操作
//QUERY为询问结点对集合
//TREE为基图有根树
Tarjan(u)
换了个姿势还是上了HDU 据学长给我的图论题库来说 lca问题也写完了
这题几乎还是模板题 只不过是多了个 判断是否在同一棵树上 用了点小技巧 再Tarjan时 把根节点也传上去 如果得结果时根节点不同就跳过
另外这题灰常容易爆内存 稍微改了一下用 C++水过去了 然而G++还是爆………………
AC Code
#include
最近一周好好把并查集和最短路走的尽量远一点 再然后就得往RMQ 差分约束 网络流方向走了
扯回来扯回来 刚写的一道带权并查集问题 （因为其实我的并查集基础很薄
并且再之前已经好几次碰到类似的问题了 就是说 带权并查集再合并两棵树的时候 他们各个节点是如何处理的 一直以来我都想不到好方法 今天刚写完这题 我才算明白算法的强大与互通性 看完其他人的博客 我马上意识到 —— 是在线段树里的 延迟更新 也就是说我先做个标记 当我访问的时候 我需要的时候再更新
而这里也是一个道理 我只对被合并的树 的根节点进行更新 当要访问这棵树的叶子节点 我再对其逐个节点递归更新 一直到访问节点
这个思路的博客其实是有很多的 但我实在是忍不住发一个 毕竟对我来说又是一大冲击
AC Code
#include
最近在水KM算法 只要把KM理解了 至今写到的大部分都是水题
唯独这题让我写了很长时间 看了其他人的博客才明白什么叫建图的巧妙和重要性
题意 有n家公司和m个任务 所有任务和公司都已经匹配好了 要求在尽量保留原有匹配的基础上 求得最优匹配 输出改变的数量 和 改变后增加的权值
巧妙的思路来了 首先对于所有输入的权值增大K倍 这里的K必须大于n 再对原匹配的权值都加 1 这样 原匹配的优先级将大于其他匹配
再套模板 这时出来的结果 将是匹配权值数的K倍再加上原匹配的数目 （所以这里就体现了K大于n的原因了 若是K小于n 那么大于K的部分将可能成为原匹配数目，结果将乱套………………
AC Code
#include
KM算法 用于求二分图的最佳完美匹配 即权值最大的完美匹配 如果你也是个刚来学习KM算法的人 大概的用途肯定还是知道的吧 还是直接说重点吧 首先 理解KM算法前 必须有以下3个概念 1.可行顶标 对于一个赋值二分图G(x,y,e,w) (x,y 代表二分图的两边顶点标号 e代表边 w代表边的权值 ) 我们对两边的每一个顶点都赋予一个额外的值 使得对于二分图G内的所有边 e=xy 均有 lx(x)+ly(y)>=w(xy) 其实不管什么样的图 什么样的边权 可行顶标必然存在 例如 lx(x)=max w(xy) ly(y)=0 2.在已经赋值可行顶标的二分图中 保留所有lx(x)+ly(y)…