已注销

dfs &am...

ACM模版篇(139) C++(4) CONTESTS(31) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章 / dfs && bfs （共59篇）

NYOJ－19－擅长排列的小明

描述小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。输入第一行输入整数N（1 < N < ...

2021-05-22

0 467

NYOJ－21－三个水杯

描述给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。输入第一行一个整数N(0< N <50)表示N组测试数据接...

2021-05-22

0 461

NYOJ－32－组合数

描述找出从自然数1、2、… 、n（0< n <10）中任取r(0< r <= n)个数的所有组合。输入输入n、r。输出按特定顺序输出所有组合。特定顺序：每一个组合中的值从大到小排列，组合之间按逆字典序排列。样例输入 5 3 样例输出 543 ...

2021-05-22

0 382

无向图找桥

ACM模版无向图找桥 /* * 无向图找桥 * INIT: edge[][]邻接矩阵；vis[],pre[],ans[],bridge置0； * CALL: dfs(0, -1, 1, n); */ const int V = 1010; int bridge; //桥 int edge[...

2021-05-22

0 470

无向图连通分支

ACM模版无向图连通分支 /* * 无向图连通分支(dfs/bfs邻接阵) * DFS / BFS / 并查集 * 返回分支数,id返回1.分支数的值 * 传入图的大小n和邻接阵mat,不相邻点边权0 */ #define MAXN 100 void search(int ...

2021-05-22

0 360

POJ－1985－Cow Marathon

ACM模版描述题解想要求最长两点距离，因为路径是唯一的，所以直接从任意一点查找距离此点最远的结点s，那么这个结点s一定是最远两点中的一点，然后再从这一点查找另一点，此时，求得的ans即为最远距离。这里使用两次BFS即可，结合邻接表使用。代码 #include <cstri...

2021-05-22

0 361

51Nod－1489－蜥蜴和地下室

ACM模版描述题解 One：首先将头尾的两个弓箭手打爆，然后dfs中间的弓箭手即可。这里需要注意，每次往后搜索N+1的条件是，第N-1个弓箭手已经被A死了，但是第N个弓箭手不要求必须死。因为这里数据很小，所以dfs暴力搜索是可以AC的…… Two：另外还可以使用动态规...

2021-05-22

0 369

51Nod－1416－两点

ACM模版描述题解深度优先搜索，这里需要强调的是，不要归置状态，只要访问过就标记为1，另外需要设置一个tag标签，标记上一步，防止下一步与上一步重合。当访问的下一步所访问的点已经被访问过，说明形成了环。代码 #include <iostream> #includ...

2021-05-21

0 368

51Nod－1109－01组成的N的倍数

ACM模版描述题解这里只强调了M>0，而没有提其上限，那么只有一种可能，就是M极大，会远远超出long long，所以我们这里需要用到BFS求出其最小的M，但是需要输出M，所以需要结合DFS输出。这里可以进行一下剪枝，定义一个vis数组用来存储余数状态，如果某一个余数出现过...

2021-05-21

0 338

NYOJ－999－师傅又被妖怪抓走了

ACM模版描述题解第一次做双BFS，有些生疏，有些想当然。一直以为最先搜索出来的就是最优的，可是对于双BFS而言，第一个BFS最先搜索出来的不一定是最优的，需要将第一个BFS搜索出来的所有结果都进行第二个BFS，从得到的答案中选取最优即可。因为没有写过双BFS，所以一开始写的代码...

2021-05-21

0 406