已注销

图论

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-1535-Invitation Cards

ACM模版描述题解每次做题都是读一遍题没读懂，然后就去看翻译……真心塞。这道题题意是求从1号结点到所有结点的最短路之和，然后再返回1号结点的最短路之和的和。比较直观的使用SPFA搞搞，但是这是单源最短路，求第一个过程很容易，可是第二个过程如果死板硬套，那么需要进行n-1次SP...

2021-05-21

0 340

HDU-1546-Idiomatic Phrases Game

ACM模版描述题解模版大法好~~~ 最短路模版题，不过需要进行一些处理来建图。题意：已知成语至少有3个汉字，每个汉字用4个字符（十六进制数）表示，成语接龙游戏，求从第一个成语接到最后一个成语的最小花费。读取字符串后，对前四位以及后四位十六进制字符进行转进制，转为10进制，存...

2021-05-21

0 430

HDU-2680-Choose the best route

ACM模版描述题解典型的最短路，想从多个车站中挑一个出发到达终点站s，要求路径最短，这里是有向图，所以，如果我们按照正向建图，则需要进行多次dij，这明显是有可能超时的，所以我们需要反向建图，然后求从终点站到其他站的最短路，最后求得最小的最短路即可。代码 #include &l...

2021-05-21

0 417

HDU-2923-Einbahnstrasse

ACM模版描述题解好长的英文题，看得我都心碎了~~~ 百度了一下大意：三个数字n、c、r，n代表城市的个数，c代表损坏的车辆的数量，r代表有几条路，然后接下去有c+1个字符串，第一个代表拖车公司的所在地，后面的c个地点表示损坏的需要拖回来的车辆所在地。在接下去r个字符串，代...

2021-05-21

0 493

HDU-2224-The shortest path

ACM模版描述题解双调旅行商问题，还不是太懂这个问题，暂时扣模版，今天晚上好好看看算导研究研究传说中的NP~~~ 代码 #include <iostream> #include <cmath> #include <cstdio> using ...

2021-05-21

0 340

HDU-1595-find the longest of the shortest

ACM模版描述题解先dij一遍，求出0到n-1的最短路径，然后枚举每一段，求出删除该段时的最短路，最后求所有情况的最短路径的最大花费。多次dij搞搞。这里需要记住的是，对dij要进行一个改造，不能每次都动pre[]（最短路路径），只有第一次求的时候才会对它下刀。最后调戏一下下...

2021-05-21

0 0

HDU-3986-Harry Potter and the Final Battle

ACM模版描述题解这道题和 HDU 1595 find the longest of the shortest一样，都是删掉任意一条边的最长最短路，不同的是，一个没有重边，一个有重边。 1595我是用邻接矩阵+dij搞的，但是这道题因为重边，所以邻接矩阵看样子不能搞，但是实际上是可...

2021-05-21

0 362

HDU-1599-find the mincost route

ACM模版描述题解求最小环，题上说的十分清楚，是无向图，所以要求环的结点最起码要有三个，也就是说，K>2，如果是有向图，那么结点最少可以是两个…… 模版题，直接套~~~用Floyd求解。代码 #include <iostream> using namesp...

2021-05-21

0 364

HDU-1839-Delay Constrained Maximum Capacity Path

ACM模版描述题解第一次做这种组合算法题，二分+dij，没做过很难想到这样子搞，于是参考了大牛shuangde800的代码和题解。该大牛的题解分析道：因为每条路径的容量取决于这条路径中所有边中的最小容量，所以我们可以以此枚举最小容量。但是如果一个一个容量的枚举，那明显效率...

2021-05-21

0 334

HDU-3631-Shortest Path

ACM模版描述题解 Floyd插点法。对于我而言，又是新题型，每次遇见新题型，总是懵逼+555… 百度吧，百度到了陈国林的题解。说一下我的大致理解吧，早先我们做的Floyd算法复杂度是O(n^3)，产生这个复杂度的原因是涉及到了起点、中间点、终点，每次需要用中间点来更新不同起...

2021-05-21

0 396