LCA

HDU 2874 Connections between cities

Posted on

换了个姿势还是上了HDU 据学长给我的图论题库来说 lca问题也写完了 这题几乎还是模板题 只不过是多了个 判断是否在同一棵树上 用了点小技巧 再Tarjan时 把根节点也传上去 如果得结果时根节点不同就跳过 另外这题灰常容易爆内存 稍微改了一下用 C++水过去了 然而G++还是爆……………… AC Code #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> using namespace std; const int maxn=10005; const int inf=0x3f3f3f3f; struct node { int v,d; no […]

带权并查集

HDU 2818 && POJ1988 Cube Stacking

Posted on

今天打比赛前写的一道带权并查集 题意 搬砖头 把包含有 a的砖头堆里的 所有砖头 转移到 包含b的砖头堆上 问 K砖头下有几块砖头 思路 :并查集 额外开两个数组 一个记录这堆砖头堆的砖头高度 另一个记录k砖头下有几块砖头 每次合并的时候更新砖头高度 和被合并的砖头堆 最底下砖头 下面有几块砖头 用户find 时更新 AC Code #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <queue> #include <algorithm> #include <cstdlib> using namespace std; const int maxn=30005; int root[maxn],u […]

带权并查集

HDU3047 Zjnu Stadium

Posted on

最近一周好好把并查集和最短路走的尽量远一点 再然后就得往RMQ 差分约束 网络流方向走了 扯回来扯回来 刚写的一道带权并查集问题 (因为其实我的并查集基础很薄 并且再之前已经好几次碰到类似的问题了 就是说 带权并查集再合并两棵树的时候 他们各个节点是如何处理的 一直以来我都想不到好方法 今天刚写完这题 我才算明白算法的强大与互通性 看完其他人的博客 我马上意识到 —— 是在线段树里的 延迟更新 也就是说我先做个标记 当我访问的时候 我需要的时候再更新 而这里也是一个道理 我只对被合并的树 的根节点进行更新 当要访问这棵树的叶子节点 我再对其逐个节点递归更新 一直到访问节点 这个思路的博客其实是有很多的 但我实在是忍不住发一个 毕竟对我来说又是一大冲击 AC Code #include <cstdio> #include <cstring> #include < […]

带权最大匹配

HDU 2853 Assignment

Posted on

最近在水KM算法 只要把KM理解了 至今写到的大部分都是水题 唯独这题让我写了很长时间 看了其他人的博客才明白什么叫建图的巧妙和重要性 题意 有n家公司和m个任务 所有任务和公司都已经匹配好了 要求在尽量保留原有匹配的基础上 求得最优匹配 输出改变的数量 和 改变后增加的权值 巧妙的思路来了 首先对于所有输入的权值增大K倍 这里的K必须大于n 再对原匹配的权值都加 1 这样 原匹配的优先级将大于其他匹配 再套模板 这时出来的结果 将是匹配权值数的K倍再加上原匹配的数目 (所以这里就体现了K大于n的原因了 若是K小于n 那么大于K的部分将可能成为原匹配数目,结果将乱套……………… AC Code #include <cstdio> #include <cstring> #include <algorithm> #include <iostream&g […]

带权最大匹配

KM 算法学习

Posted on

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)=w(x)(y) 的边 删去其他的边 形成的新的图称为生成子图 3.在生成子图中的任意一个完美匹配都是最佳完美匹配 反过来 G的任意一个最佳完美匹配都包含在 生成子图中 可能第三条定理来的有些突然 […]

BFS

HDU 4634 Swipe Bo

Posted on

玛德 我现在特别想骂人 这道题真特么的坑爹 坑爹 坑爹 航电你就不能吧数据搞的好一点么 写了我几乎整整一天 我也不想多说什么了 真的 让我静静 这时间浪费的太不值了………… #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> using namespace std; char g[220][220]; int sx,sy,ex,ey; int row,col,keynum; bool flag[202][202][1<<7][4]; int mve[][2] = {{-1,0},{0,-1},{1,0},{0,1}}; struct no […]

最大匹配

HDU 1350 Taxi Cab Scheme

Posted on

题意: 老司机接客的故事 有很多顾客想要去一些地方 给你起点和终点 问最少需要多少老司机 (起点不计时 主要是坐标建图还是第一次写到 就写个题解压压惊 其实还是按照题意来就好了 再用数组链表实现邻接表存图 好像写烦了 慢了点 #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std; const int maxn=505; int n,cnt; int head[maxn],link[maxn]; bool vis[maxn]; struct point { int x,y; }; inline int dist(const point& a,const […]