sunny_forever

分类

题解(57)

/ 注册

全部文章（共57篇）

题解 | #旅行#

思路枚举中转点，当中转点为 i 时对应得到：res_i = f[i][0] + f[i][1]那么最终的答案 res = max(-1，res_1，res_2，res_3，...... ，res_n)f[i][0]：点 i 可到达的最远点(记其为x) 与点 i 之间的距离f[i][1]：点 i ...

最短路小根堆预处理

2021-07-14

1 567

题解 | #迷宫2#

思路题意：求让蜥蜴没办法达到终点所必须花费的最小总代价我们通过把特殊的走道转化为墙壁（转换代价为g[i][j] ），来使蜥蜴最终无法到达终点 g[i][j]取不同值的意义：-1代表墙壁，0代表走道，而1到10^9之间的正整数代表特殊的走道。因为 g[i][j] = -1 代表已经是墙壁，故转...

最短路思维

2021-07-11

7 890

题解 | #Rinne Loves Dynamic Graph#

思路求从 1 到 n 的最短路，需注意的是图上所有边的边权会实时改变如何改变：每次走过一条边之后，所有的 x 都会执行一次操作：x = 1/(1-x)，x 是边权，所有的 x 指所有边即边权会随着走过的边的数目的改变而改变所以该题不再仅仅是最短路问题，而是变成了最短路 + dp 问题...

最短路 dp 思维

2021-07-10

1 469

题解 | #Rinne Loves Graph#

思路求能从 1 号点到达 n 号点并且满足相关条件的最短路条件：穿过的被***城镇不能超过 K 个解法：最短路＋ dp dist[i][j]：从起点开始穿过了j个被***的城市到达i点的最短距离ps：dist 最后一定是最短距离，但中间过程的值不一定是，因为后续可能被再次更新所...

最小生成树 dp

2021-07-09

6 665

题解 | #小雨坐地铁#

根本不需要分层图，其实是dijkstra模板题思路让我们求从 s 到 t 的最短路关键点在于建边有手就行很简单一题，不废话了，代码如下 Code #include <bits/stdc++.h> using namespace std; const int N = 1e3...

最短路

2021-07-09

6 668

题解 | #Forsaken喜欢独一无二的树#

题意删除一些边，使得最小生成树唯一，问删除的边的权值和最小是多少？思路为什么最小生成树不唯一：因为连接相同两个集合的边，权值相同的可能有多个所以，我们只需要删除权重相同的且连接同两个集合的那些边即可：这些边中留一个用于维持最小生成树，其余的均删掉。因为是稀疏图，所以使用 Kru...

最小生成树并查集

2021-07-08

1 536

题解 | #银河英雄传说#

思路并查集即可 .问题在于如何求两个战舰之间的战舰数目 ? 我们使用 d[ ] 和 num[ ]来辅助我们解决上面的问题d[i]：i 距离根节点（队头）的距离num[i]：i 所在的连通块有多少个元素（ i 所在那一列的战舰数目） Code #include <bits/stdc+...

并查集

2021-07-08

2 499

题解 | #[NOIP2001]Car的旅行路线#

题意求从城市 A 到城市 B 的最少花费：最短路已知一个城市有四个机场，不妨令 A 城市中的四个机场为 a1 , a2 , a3 , a4 ，B 城市的为 b1 , b2 , b3 , b4 又因为各个机场彼此互通，所以本质是求: min ( d[a1][b1], d[a1][...

最短路

2021-07-08

1 766

题解 | #[HAOI2006]聪明的猴子#

题意求出满足条件的猴子的数目，满足的条件是：能在这个地区的所有树冠上觅食换成用数学语言来描述条件：猴子的最大跳跃距离 MaxD 需大于或等于最小生成树边集中最长的那条边最小生成树：联通该地区所有的树冠所形成的最小生成树思路 prim 算法扫一遍，在这个过程中，求出最小生成树边...

最小生成树

2021-07-08

2 563

题解 | #[NOIP2009]最优贸易#

题意在从 1号点到 n号点的路径中，选择两个城市 A 和 B，必须先选 A 再选 B，问能赚取的差价最大是多少A：买入水晶球B：卖出水晶球 ps：1 号点到 n 号点的路径可能不止一条 . 思路不妨遍历 n 个点，对于每个点求出 res_i = w2[i] - w1[i]w1[i]：买入...

预处理 dp 最短路

2021-07-08

2 554