POJ 1904 强连通分量 POJ 1904 题意给出一个匹配表.n个王子,接下来n行.行首代表王子喜欢$k$个公主,接下来是$k_i$个公主的编号.最后一行给出当前一种 : 与每个王子结婚的公主编号(喜欢才能结婚).所有王子都要结婚 求可以与每个王子结婚的所有公主编号(并且所有王子都要结婚) 思路 若王子u喜欢公主v,u->v建边 由最后一行的一种结婚情况来反向建边; 王子u与公主v结婚,v->u; 建 2019-10-01 算法
POJ 1486 最大匹配 POJ 1486 题意平面上给出几张幻片灯.且包含一些数字.找到可以确定唯一数字对应的幻片灯(矩形内), 思路 在dfs求出每个数字所匹配的幻灯片后.还要确定该匹配边的唯一性.即如果去掉该边.重新匹配且最大匹配数未变.则说明该匹配边不是唯一的. 输出能够确定的数字的幻灯片.所有幻灯片都无法确定则输出none 构造一个struct {} edge[];来存所有第一次df 2019-10-01 算法
HDU 4635 强联通分量+缩点+思维 HDU 4635 问题:给定一个有向图,问最多添加多少边后,该图仍然不是强连通图? 如果已经是强连通图则输出-1 思路: 在每个强连通子图中添加边不影响该图变成强连通图(所以可以任意添加).那么将强连通子图缩成点来分析 保证不变成强连通图,那么合并到只剩下2个强连通子图(点),且2点间只存在单向边（单向边说明点的入度或出度=0）能够使得添加的边最多 证明: 如果剩下3个强连通子图(点),必 2019-09-27 算法
HDU 4612 边双连通+缩点 2 处理重边问题 HDU 4612 问题： 无向图将边双联通分量缩点后添加一条边使得割边数量变得最少,最少是多少? 思路: 在2个距离最远的点添加一条边使得割边消失的最多,那么剩下的割边最少 先dfs一次找到距离最远的2个点中的1个.(同时记录缩点后割边的总数), 再一次dfs就能统计到另一个最远点的路径上的割边数量. 技巧 for (int j=head[i]; j!=-1; j 2019-09-27 算法
HDU 4738 割边模板 HDU 4738 裸求割边的存在一起割边中的最小值 割边不存在输出-1 图不是连通图,则已经达到题目条件.士兵花费为0 坑点: 割边存在最小值为0,需要一个士兵抗炸弹 割边模板 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545 2019-09-26 算法
POJ 3694 割边+lca POJ 3694 问题 连通图中给出q个询问,每次询问添加一条边,问添加后割边的数量? 思路 trajan求出割边数量(标记割边中的一点:等价于缩点后存在的点)。 给出的连接2个点到lca的边上的割边都要取消掉(因为成环了,所以环上不存在割边了) 看题解学的LCA (最近公共祖先) tarjan时顺带求出搜索树中每个点的深度,lca时先将2个中的深的向上遍历,使得2个点在同一深度。再同时向 2019-09-25 算法
欧拉图 拥有欧拉回路的无向图称为欧拉图无向图从点S出发能够不重不漏的经过每条边一次(可重复经过图中节点)最后回到点S**称该路径为欧拉回路**, 邻接表存图 dfs用栈保存回溯的点,最后栈的逆序就是欧拉回路 技巧 数据栈模拟递归 访问一条边后head[x] = next1[i]将点x的第一条边改为下一个未访问的边,每次取出head[x]可以避免拿到访问过的边 POJ 2230 题目要求 2019-09-25
文本查询程序(类的继承体系) 单词查询的基础上实现3个逻辑查询 ~得到所有不匹配的行 &将2个匹配结果取交集 |将2个匹配结果取并集 表达式查询:Query("xx") & Query("xx") | Query("xx")如何抽象出基类 且 定义接口类 TextQuery已经实现了单词查询,如果剩下的3个操作通过TextQuery派 2019-09-22 C++primer读书笔记
string简化版allocator分配内存 通过allocator类来分配内存实现简化版string功能: String(const char*)和String(const std::string)接受隐式类型转换 重载string的多种运算符:[],+,+=,<<,>> 实现string多个成员函数size(),等 构造函数和析构函数对原始内存的分配和释放, 内存分配问题 allocator<>类 2019-09-15 C++primer读书笔记
动态内存管理类StrVec的实现 实现一个动态内存管理类 StrBlob中vector<string>可以管理元素的内存. 实现一个vector<string> allocator<>类是分配的原始内存,当调用alloc.destroy(first_free), 按道理来说destroy执行对象的析构函数,string的析构函数执行完后会回收内存,再访问该string就访问越界了 但是如果 2019-09-14 C++primer读书笔记