已注销

图论

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

/ 注册

全部文章 / 图论（共96篇）

HDU-2874-Connections between cities

ACM模版描述题解 LCA问题，有离线和在线两种解法，这里使用的是在线ST算法，需要注意的是，这里的不是一个连通块，所以需要进行多次dfs()，一次LCA_init()就行了，另外这里需要用到并查集，因为两个点没有连通时要输出Not connected，而判断是否连通并查集最合适了（最...

2021-05-21

0 466

HDU-1548-A strange lift

ACM模版描述题解猛一看，是经典的bfs啊，当然，bfs真的可以滴，但是这是在最短路专题的，然后转念一想，真有趣啊，只要把能连通的全部置为1，这样不就可以求最短路了？这是个谜一样的题，好久前做过相似的题，我却没有想到可以用最短路搞搞！！！代码 #include <iost...

2021-05-21

0 302

HDU-2544-最短路

ACM模版描述题解基础最短路，只要会套模版，就能A。代码 #include <iostream> #include <cstring> using namespace std; /* * 单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(...

2021-05-21

0 575

HDU-3790-最短路径问题

ACM模版描述题解虽然是最短路，但是有坑，首先题目中没有提到重边问题，这里需要先判断重边，去除重边，接着，要求，满足路径最短的情况下花费最小，一开始是先求最短路，然后把最短路上的花费累加起来，后来发现，这是错误的，因为有可能存在最短路不止一条，所以需要求最小的花费，所以，不能把这两部...

2021-05-21

0 552

HDU-2066-一个人的旅行

ACM模版描述题解很基础的最短路，可是有些逗逼的是，需要默认草儿家到相邻城市花费为0，草儿家也可以默认为0号城市。代码 #include <cstdio> #include <cstring> #include <algorithm> us...

2021-05-21

0 363

HDU-2112-HDU Today

ACM模版描述题解字典树+最短路即可，糟糕的题目，表达有些问题，导致理解错了N……，还是我太渣了。一开始以为需要搞个N*N的矩阵（代码One），会爆内存，然后就用了堆优化（邻接表，代码Two），可是因为没有正确理解N的表示，还是超时了，改了改对了。代码 One： #inc...

2021-05-21

0 262

HDU-1874-畅通工程续

ACM模版描述题解最短路搞搞事情啊~ 代码 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; /* * 单源最短路径，Dijkst...

2021-05-21

0 589

HDU-1217-Arbitrage

ACM模版描述题解真是炸了，题倒是十分简单，无非是求任意两点之间的最短路（变种，其实不是求最短，而是求最大连乘），之间用Floyd搞搞就行，可是，我一开始用结构体存储，却一直出现bug，到现在我都没有找到问题在哪儿（代码One），求大神们一瞥，给予我些许建议…… 之后，我只好把结构...

2021-05-21

0 403

HDU-1245-Saving James Bond

ACM模版描述题解给定一个100X100的池子，中间(0, 0)处有一个直径为15的岛，然后湖中有许多踏点，问能否踩着踏点蹦跶出来，当然，有一个最远的蹦跶的距离d。思路很清晰，最短路，只要求出两两点之间的距离加以处理，然后把岛当做源点，湖外当做终点，添加与其他点对应的路径信息即可...

2021-05-21

0 547

HDU-1317-XYZZY

ACM模版描述题解先使用Floyd扫描一遍，判断连通性，然后使用BellmanFord算法跑跑就可以了。这里一开始有些懵逼，搞不懂为啥要用Floyd，因为只求1~n的连通性不必要用Floyd啊，还那么慢，后来仔细看发现，后边判断是否有正环时还要使用到其他点之间的连通性，所以呢，F...

2021-05-21

0 363