coder-River
coder-River
全部文章
分类
归纳(12)
题解(82)
归档
标签
去牛客网
登录
/
注册
River的博客
万物皆可Restart~
TA的专栏
98篇文章
0人订阅
Re:从零开始的刷题生活
85篇文章
858人学习
Re:从零开始的归纳时间
13篇文章
1066人学习
全部文章
(共94篇)
Uva 567 进来复习Floyd算法模板
来自专栏
一、题意 每组数据有20个城市,给出每个城市与之相邻的城市,距离为1,不相邻的城市认为不可达。然后有q个询问,每次询问任意两个城市之间的距离。 二、解析 由于要询问任意两个城市之间的距离,因此这是一个多源最短路问题,即需要得到每两个点之间的最短路。这样的问题只能使用Floyd算法。算法复杂度为O(n...
2020-09-04
0
486
Poj 3259 进来复习spfa算法模板
来自专栏
一、题意 农夫有n块田地, 编号 1...n(1<=N<=500),田地间有m1条双向路径,每条路径有一个经过所需要的时间wi。同时有m2个单向虫洞, 每条虫洞走完后时间倒回wi。问农夫是否能在田地中遇到以前的自己。 二、解析 这道题的情景非常有意思,m1条双向路径的权值为w,而m2条...
2020-09-04
0
434
Poj 2397 进来复习Dijkstra算法模板
来自专栏
一、题意 输入一个n个点m条边的无向图,每条边给出边权,求从点1到点n的最短路径。 二、解析 最短路径模板题。用来复习一下Dijkstra算法的模板正好。Dijkstra算法的时间复杂度为O(mlgn),一般对于边权为正的单源最短路问题就它就没错了。同时适用于有向图和无向图。 三、代码 #inclu...
2020-09-04
0
487
[图论] 最短路问题归纳
来自专栏
基本原则 首先看题目n的数量级,当 n<1000 时,可以使用 [Floyd算法] 快速秒杀几乎所有题型 否则 若题目中所有边全为正权,则使用 [Dijkstra算法] 否则 当出现负权时,使用 [spfa算法] 注意一些隐蔽的最短路问题,比如题目会换一种问法。详见最短路的各种变形题。...
2020-09-04
0
823
Uva 1395 最“苗条”的生成树
来自专栏
一、题意 给出一个n(n<=100)结点的图,求苗条度(最大边减最小边的值)尽量小的生成树 二、解析 其实就是要求边权极差最小的生成树。我们知道求最小生成树是用Kruskal算法,这里其实也是一样:我们枚举生成树的最小边E[l],然后每次只从边权大于这条最小边边权的边中进行最小生成树的生成,这...
2020-09-04
0
599
Uva 10600 进来复习一下次小生成树的算法
来自专栏
一、题意 输入一个n个点m条边的图,要求你计算出图中的最小生成树和次小生成树的权值和。 二、解析 最小生成树比较简单,直接上Kruskal算法模板即可。主要是次小生成树应该如何求解? 其实也比较简单,按照以下步骤即可: 求出最小生成树mst 通过以每个点为根分别进行dfs,得到maxW[maxn]...
2020-09-04
0
425
Uva 10034 进来复习一下最小生成树模板
来自专栏
一、题意 输入n表示有n个点,然后输入每个点的实数坐标(xi, yi),求连通所有点的最小长度和。 二、解析 这是一道裸的最小生成树问题,边权就是两点间的距离。直接上Kruskal算法模板。总是得来一道模板题复习复习的。 三、代码 #include <iostream> #include...
2020-09-04
0
582
[枚举] 暴力求解之枚举方法归纳
来自专栏
一、枚举排列 1. 定义 枚举出一个序列a[maxn]的所有排列。 2. 解析 枚举排列 最简单的方法是运用STL的 next_permutation函数. 3. 模板 int a[maxn]; int main(){ ...... sort(a, a + n); ...
2020-09-04
1
1066
[经典] 常见的高效算法归纳
来自专栏
一、滑动窗口 1. 定义 滑动窗口法(又叫双指针法),即用i,j双指针(一般用下标)对数组进行遍历,同时要需要一个额外的比如vis数组维护窗口中的元素信息,是一种O(n)的扫描方法。 2. 解析 一般比较常见的问题就是,维护窗口中的元素各不相同。既可以用一个vis[maxn]数组来表示窗口中是否存...
2020-09-04
0
395
[动态规划] 背包问题归纳
来自专栏
一、01背包问题 1. 定义 有n件物品和一个容量为V的背包。第i件物品的体积(volumn)是v[i],价值(worth)是w[i],问如何选择物品装入背包可使价值总和最大。 2. 解析 每种物品只有选和不选两种。我们可以使用多阶段动态规划的思想来解决。用dp[i][j]表示前i个物品(或用“从...
2020-09-04
0
634
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页