在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

全部文章 / 题解（共13篇）

题解 | #逛公园#

本题要求求路径数，图论的最短路算法可求不了路径数，那么可以想到在图里面使用动态规划的方式去求路径数。在本题里面可以得出从某一点到下一点的路径方式有多少取决去这一点之前的路径数，以及该点和下一点的路径数。那么就可以知道之间可以使用动态规划去求解。但本题有要求路径长度不能超过n+...

C++ 动态规划迪杰斯特拉算法图论最短路径

2023-11-16

2 400

题解 | #[SCOI2012]滑雪与时间胶囊#

本题中a180285的时间胶囊操作其实相当于随意的去走一个树形的结构。那么很容易就想到了最小生成树算法。但是由于本题中必须从高度高的向高度低的去走。而且图是一个有向图，所以在这里克鲁斯卡尔算法不适用，因为克鲁斯卡尔算法的加边方式不会去在乎单向边的问题。那么使用prime算法，但是优先...

C++ 图论最小生成树克鲁斯卡尔算法

2023-11-12

0 438

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

由克鲁斯卡尔算法可以知道，将边排序后一股脑的加入到最小生成树里面，只要没有回路就是最小的生成树。那么排序过后可能会有一些边是长度相同的，这些边有可能不适用于当前的生成树，但正因为这些长度相同边的存在才导致最小生成树不唯一。那么将这些无法加进最小生成树，但长度相同的边删除就是结果。 ...

C++ 图论最小生成树克鲁斯卡尔算法

2023-11-12

1 318

题解 | #道路建设#

//最小生成树模板题，用普利姆算法或克鲁斯卡尔算法求解。 #include <bits/stdc++.h> using namespace std; #define int long long const int&nb...

C++ 图论最小生成树普利姆算法克鲁斯卡尔算法

2023-11-11

2 353

题解 | #[HAOI2012]ROAD#

通过建立糖果数变多的有向图来由拥有糖果数最少的那个人下手去计算出每个小朋友的最小糖果数。那么在这里增加一个0点当做起点，然后可以从起点出发求出每个点的最小糖果数。由于在这里我们差分的值就是最小值，所以我们要求尽量满足差分条件。那么我们在寻找的时候就要去寻找最大值。这样可以让每一条边的条件都...

C++ 差分约束图论 SPFA算法

2023-11-11

1 369

题解 | #Ranking the Cows#

//本题首先的困难在于要明白如果想知道一个序列的排序序列再不考虑传递影响的情况下需要有n(n-1)/2个大小关系。 //本题给出的大小关系里面有受传递影响可以推导出的一些大小关系，比如：2>1,1>4得到2>4; //那么将其扩展到n(n-1)/2里面的所有关系，也就是说需要求出间...

C++ 图论二进制优化

2023-11-09

1 382

题解 | #传送门#

这题还是再考最短路算法，在这里还是迪杰斯特拉。但难点在于建图，在这里将同一种种类的传送门具化成一个点，拥有这个传送门的可以通过这个传送门进行到达。但在花费上是二倍。还有就是不要使用map<pair<int,int>,int>来保存边。这个数据类型操作会导致这道...

C++ 图论迪杰斯特拉算法最短路

2023-11-08

0 594

题解 | #胖胖的牛牛#

因为正在练习图论，所以建图来做吧。可以假设某个各种的上下左右方向都有一个点，那么这些点的道路里面方向改变的，也就是某个格子上下左右相邻直接的道路的长度是1，其余是0。那么就可以转化成起点的四个方向点到终点的四个方向点的求解。那么直接套Dijkstra算法即可。就是建图有那么亿...

C++ 深度优先搜索图论迪杰斯特拉算法

2023-11-06

1 293

题解 | #挖沟#

最小生成树模板题。 prim算法： #include <bits/stdc++.h> using namespace std; const int maxn = 2*500000+10; const ...

C++ 图论普利姆算法克鲁斯卡尔算法

2023-11-06

2 347

题解 | #Rinne Loves Graph#

//迪杰斯特拉算法配合上动态规划 //动态规划的数组为：dp[i][j]。表示到达第i号城镇，穿过了k次所走的最短路 //一定要注意迪杰斯特拉将优先队列里面已经作为最短判断过了不要再判断了。否则会发生很奇怪的错误。 #include <bits/stdc++.h> using&...

C++ 图论动态规划迪杰斯特拉算法

2023-11-02

1 368