已注销

图论

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篇）

NYOJ-1238-最少换乘

ACM模版描述题解和今年天梯赛 L3-2 题面很像，但是更加简单一些。这个题只是一个单纯的最短路，不过我们需要先对路线进行一个比较特殊的建图处理，比如说， 4 7 3 6 ，我们应该在 4 7 、 4 3 、 4 6 、 7 3 、 7 6 、 3 6 之间都连一条线，权值为 1...

2021-05-21

0 0

NYOJ-1239-引水工程

ACM模版描述题解这个题用最小生成树的两个经典算法都可以过，用 Prim 算法相对容易写，只要再不断扩展的过程中判定究竟是建站消耗高还是建管道高，如果用 Kruskal 算法的话，则需要在生成最小树的过程中存树，然后 dfs 一遍做和前者同样的判定即可。我用的是第二种，但是其实 ...

2021-05-21

0 339

NYOJ-1252-世界之威

ACM模版描述题解一开始打算反向建图，后来发现多此一举，甚至可能更加麻烦，所以还是正向建图，不过这里的图比较特殊，建好后包括三种结构——链、环、集中（我瞎叫的，就是一个点连着多条链，链方向都指向中心点）。其实这三种结构可以归为两种，链和环，只要把第三种结构拆分为数条链就好了。接着进行...

2021-05-21

0 362

河南第十届ACM省赛-I-Transmit information

ACM模版描述题解十分有趣的一道题，可以用 dp 解，也可以用倍增法 Floyd 解，标程是后者。这里是求经过 N 条边的最短路，简单的最短路算法已经无法满足需求，我们需要对图进行 N 次 Floyd，由于每次 Floyd 都不是直接对原花费矩阵操作，而是将值存在另一个矩阵中，所...

2021-05-21

0 297

蓝桥-ALGO-25-Car的旅行路线

ACM模版描述题解说起蓝桥杯，虽然现在搞得越来越大了，可是一点不走心，官网的 OJ 做得垃圾透了，好好一个题给的样例都是错的，真是扯啊~~~ 这个题其实就是一个建图+Floyd，建图比较麻烦一点，其中比较核心的是已知三点求矩形第四点，这个我用的是先求出三角形的直角顶点，然后根据一个...

2021-05-21

0 354

计蒜客-2017 计蒜之道复赛-D-百度地图导航

ACM模版描述题解最短路问题，模版题，SPFA 可以过，BF 应该也可以过的~~~ 这里的难点不在于求最短路的过程，而是建图的过程，比赛时懵逼了，怎么也建不好，无限 MLE，赛后想到了可以通过建超级源点和超级汇点来辅助建图。每一个城市群都添加一个超级源点通往任意城市，花费为 0...

2021-05-21

0 379

CF-Codeforces Round #420 (Div. 2)-D-Okabe and City

ACM模版描述题解这个题真的有趣，最短路，难点主要是在建图上~~~ 这里先说一下题面的误区，我一开始理解为每盏灯只能点亮其所在的行或者列，谁成想并不是这样，而是说能点亮任何行或者列。那是否意味着我们需要考虑他和任何一行或者一列的边呢？实际上并不需要，因为题目中有一个很强的条件，...

2021-05-21

0 333

HDU-5883-The Best Path

ACM模版描述题解给定一个无向图，关于欧拉路的问题。这里我们要求的是这个路径的结点异或在一起的最大值。首先，我们可以通过判断度的奇偶性来判断是否是 Impossible ，因为欧拉路径存在两种，一种是欧拉通路，一种是欧拉回路。通路是起点、终点是不同点，那么我们需要将起点终点多算...

2021-05-21

0 321

HDU-5889-Barricade

ACM模版描述题解给定 n 个结点和 m 条路径，路径的长度均为 1 ，破坏每条路径都有对应的代价，然后会有怪兽从 m 往 1 <script type="math/tex" id="MathJax-...

2021-05-21

0 349

51Nod-1456-小K的技术

ACM模版描述题解十分好的一道题，强连通分量 + 缩点 + 并查集。这也是我做过的第一道关于强连通分量的题，所以我肯定需要找一下大牛们的题解进行参考，找到了一个大神的博客，讲得细致至极，感觉很受用，分享给大家。 mengxiang000000 ‘s blog 我断然无法写得比大神...

2021-05-21

0 0