算法的网 1（持续更新）
2026-04-01 19:38:55
发布于：上海
由于字数太多，导致在这里打字会很卡，会新开一个帖子。
观前须知：
1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意。
2.每一句话的基础是作者浅薄的知识储备。如果你认为我讲的不对，欢迎指正。但是请友好用语。因为作者心理素质奇差无比。
————————————————————————————————————————
算法是一张网。
我学习过的：
背包DP 区间DP 树形DP 状压DP 线性DP
BFS DFS 剪枝 记忆化搜索
最短路 最小生成树 差分约束 连通块 多层图（？）
并查集 堆 树状数组
单调队列 前缀和 栈 队列 ST表 差分 单调栈
最大公约数gcd 扩展欧几里得
模拟 贪心 递推 倍增 二分 递归 枚举 分治 排序 STL
树的遍历 lca
然后要把它们之间的逻辑一一梳理开，合并在一起。
由于 我在备考GESP八级。所以 会优先考虑 目前在弄的算法。
所以先从最短路开始。
我会做难度从黄到蓝的最短路，并且逐一进行认真的分析。
这里可能会放一些一个算法单独出现的题目。首先是为了难度铺垫。其次是，用这些题目加深对这个算法的理解，从而更好地与其他算法相结合。
一.最短路
最短路有很多种。可以从很多个方面来区分。
比如说分成单源最短路，多源最短路。
比如说分成dijkstra，SPFA，FLOYD。
接下来，我们一题一题分析它的易错点和用处。
先从用的最多的dijkstra入手。
一切的一切先从模板开始吧。
单源最短路模板（dij)
好想学花滑啊喵。小祈真可爱。
但是不太行。
总觉得计算机是有些枯燥和无聊的。但是既然选择了这条路，就坚定不移的走下去。
每通过一题，就想象自己实在聚光灯下谢幕了一次。
”正因为如此，我才站在这里。“
这个是模板代码，我在字里行间做了批注易错点。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;//优先队列的定义符号标准与sort相反
}
};
priority_queue<Node>pq;
vector<Node>v[N];
int dis[N];
bool vis[N];
int main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y,zz;
cin>>x>>y>>zz;
v[x].push_back({y,zz});
//注意是无向图还是有向图
}
pq.push({s,0});
for(int i=1;i<=n;i++)dis[i]=INT_MAX;//注意赋值的是intmax还是longlongmax
dis[s]=0; //起点赋值为零
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;//vis数组赋值
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to])pq.push({to,dis[to]});
}
}
}
for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
return 0;
}
前面忘记分析算法的时间复杂度了。现在闪现一下。
这个其实是dijkstra的优化版本。
dijkstra使用贪心策略，每次选取距离起点最近的为便利顶点作为松弛顶点。（from yuilice)
普通的dij是直接枚举。时间复杂度为O(n^2)。
优化的dij使用优先队列进行筛选，时间复杂度为O(nlogn)。
我看着 天上的星 晦暗 晦暗如你。
”若以物喻己，恰似秋之萤。“
若以物喻你，恰似南山雪。
这道题不算难。大致思路是，将直接同行路径视作花费为零的路径。然后每个点的价值是d。求取最大价值。
等一下。这道题好像要用SPFA。
那我们顺带着把SPFA模板放一下好了。
啊。”若以物喻己，恰似秋之萤。“
老师说我的小说总是青春伤痛文学。从六年级到八年级都没变过。
但是我就喜欢这种感觉。本该是热烈的年龄有着不应该背负的痛苦。
不是成年人血淋淋的痛。但是是清淡的飘渺的如影随形的。
像是下了一场小雨一样。开始下了就没停过。
我累累累累累累累。但是这是我自己选的路。打碎了牙和着血吞进肚子里都得走下去。
我操了。我编译器炸了。花了半小时去调编译器。
这就是一道比较普通的SPFA模板题目。
比较特殊的是，它初始最大值要求要赋值为1e9。不然会错。
#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
struct Node{
int z,q;
};
vector<Node>v[N];
queue<Node>q;
int dis[N];
bool vis[N];
int main(){
int n,m,s,t;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y,zz;
cin>>x>>y>>zz;
v[x].push_back({y,zz});
}
for(int i=1;i<=n;i++)dis[i]=1e9;
dis[s]=0;
vis[s]=1;
q.push({s,0});
while(!q.empty()){
Node sum=q.front();
q.pop();
int k=sum.z;
for(int i=0;i<v[k].size();i++){
int len=v[k][i].q;
int fto=v[k][i].z;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to]){
vis[to]=1;
q.push({to,dis[to]});
}
}
}
}
cout<<dis[t];
return 0;
}
（其实这个例题我找的不是特别好。应该用判断负环的那种试试看。）
好的，岔子结束，我们继续赚钱。
“被神明青睐的人。”
先放代码。
#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
struct Node{
int z,q;
};
queue<Node>q;
int dis[N];
bool vis[N];
vector<Node>v[N];
int js[N];
int d,p,c,f;
int ans=INT_MIN;
void solve(int sta){
while(!q.empty())q.pop();//多测清空
for(int i=1;i<=c;i++){
dis[i]=INT_MIN;
vis[i]=0;
js[i]=0;
//多测初始化
}
dis[sta]=d;
q.push({sta,dis[sta]});
vis[sta]=1;
while(!q.empty()){
Node sum=q.front();
q.pop();
int k=sum.z;
js[k]++;
ans=max(ans,sum.q);
if(js[k]>c){
ans=INT_MAX;
return;
}
vis[k]=0;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]<dis[k]+len+d){
dis[to]=dis[k]+len+d;
if(!vis[to]){
vis[to]=1;
q.push({to,dis[to]});
}
}
}
}
}
int main(){
cin>>d>>p>>c>>f;
for(int i=1;i<=p;i++){
int x,y;
cin>>x>>y;
v[x].push_back({y,0});
}
for(int i=1;i<=f;i++){
int x,y,zz;
cin>>x>>y>>zz;
v[x].push_back({y,-zz});
}
for(int i=1;i<=c;i++)solve(i);
if(ans!=INT_MAX)cout<<ans;
else cout<<"orz";
return 0;
}
这边大致的思路前面其实已经做过的分析了。
要用SPFA的原因是可能有“负环”。
我做了一点手脚。
将求最短路变成了求“最长路”。
所以负环打了双引号。
这边的负环指的是它可能会越来越大。
分析：
这道题目是纯SPFA，没有混合任何其他的算法。
那么，能分析的点就在于其思路。
这题主要的思路是两层：
1.将P条单向路径算成是花费为零的路。
2.用“最短路”的壳，求取最大值。
这给我们启示：
“最短路”并不只能是求取图上问题的算法。也不是只能够求取最短路的算法。
它是求“最值”的算法。
时间复杂度分析（不保证一定分析的是对的。因为我很不擅长分析这个）：
（前面已经分析过了DIJ现在直接分析SPFA）：
对于每一个点，最坏的情况它可能会被放入队列m次（边的数量）（因为SPFA是争对有负环的题目，所以这种情况是很有可能发生的哦）
那么（最坏）时间复杂度是O(nm)。如果n>=1e6且m>=1e5。
那么你就会超时。
所以用SPFA需要谨慎行事。
然后我们接着看下一题。
（我大概会做五六道黄题，然后步入绿）
请柬
“飞鹰”。人生在世，不过**二字。哈哈哈哈哈哈。
额。这道题的题目其实有点容易误解。
不过可以看样例。
这道题说人话就是：求出点1到所有点的距离。求出所有点到点1的距离。将它们加起来。
唯一的问题是。它是单向边。而。如果。
要跑一遍所有顶点的最短路。毫无疑问。会超时。
那么此时，我们找出题目的弱点：它只要所有点到点1的距离。
而不对其他店的距离做要求。
我们得出结论：反向建边。然后再从点一跑最短路。
好的差不多了。
上代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
struct Node{
int z;
ll q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v1[N];
vector<Node>v2[N];
priority_queue<Node>q;
ll dis[N];
bool vis[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
ll zz;
cin>>x>>y>>zz;
v1[x].push_back({y,zz});
v2[y].push_back({x,zz});
}
for(int i=1;i<=n;i++){
dis[i]=1e18;
vis[i]=0;
}
q.push({1,0});
dis[1]=0;
while(!q.empty()){
Node sum=q.top();
q.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v1[k].size();i++){
int to=v1[k][i].z;
ll len=v1[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to])q.push({to,dis[to]});
}
}
}
ll ans=0;
for(int i=1;i<=n;i++)ans+=dis[i];
for(int i=1;i<=n;i++){
dis[i]=1e18;
vis[i]=0;
}
q.push({1,0});
dis[1]=0;
while(!q.empty()){
Node sum=q.top();
q.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v2[k].size();i++){
int to=v2[k][i].z;
ll len=v2[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to])q.push({to,dis[to]});
}
}
}
for(int i=1;i<=n;i++)ans+=dis[i];
cout<<ans;
return 0;
}
嗯。大概就是这样。
不过我卡了很久的一点是：开longlong。
开longlong是很容易开不全的。所有的一切与边权相关的东西，都是要开long long的。
所以要开longlong的题目最好是先静态检查三遍。
分析：
这道题也依然是DIJ独奏。
那么也还是单独分析思路的环节。
这边思路最显著的点就是：反向建边。
但如过只是局限于将它作为技巧，它的应用场合，可能并不是非常广泛。
所以，我们要尝试将技巧转化为思想。
这个思想就是：
当题目需要重复使用n遍相同技巧，而最后要求的结果又并不是苛刻的，反而是集中于一点的或者可以突破的；那我们要尝试一些做法，使其得以一次运行出想要的结果。
往往这个方法就是从另一个角度去想，去建边，去构图。
最短路补充：
OK。开下一题。
新年好
额。注意到一共只有五个目的地。
所以。我们可以考虑，将五个目的地的最短路全部预处理出来。
然后。进行1-5全排列DFS。
差不多。
上代码。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int ng[10],n,m;//need to go目的地
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
vector<Node>v[N];
int dis[10][N];
bool vis[10][N];
void solve(int sta){
for(int i=1;i<=n;i++){
dis[sta][i]=INT_MAX;
}
int s=ng[sta];
dis[sta][s]=0;
pq.push({s,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[sta][k])continue;
vis[sta][k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[sta][to]>dis[sta][k]+len){
dis[sta][to]=dis[sta][k]+len;
if(!vis[sta][to])pq.push({to,dis[sta][to]});
}
}
}
return;
}
bool dv[10];
int ans=INT_MAX;
void dfs(int x,int now,int whe){
//现在正在哪个节点上，
dv[whe]=1;
if(x==5){
ans=min(ans,now);
return;
}
for(int i=1;i<=5;i++){
if(!dv[i]){
dfs(x+1,now+dis[whe][ng[i]],i);
dv[i]=0;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=5;i++)cin>>ng[i];
for(int i=1;i<=m;i++){
int x,y,zz;
cin>>x>>y>>zz;
v[x].push_back({y,zz});
v[y].push_back({x,zz});
}
ng[0]=1;
solve(0);
for(int i=1;i<=5;i++)solve(i);
for(int i=1;i<=5;i++){
memset(dv,0,sizeof dv);
dfs(1,dis[0][ng[i]],i);
}
cout<<ans;
return 0;
}
本题的难点是：代码有点难调。
其他的没了。
分析：
依旧是最短路单打独斗。
欸不对。
本题是DFS（全排列）+最短路的做法。
不过DFS是基础DFS，如果要在DFS上再做手脚，这题就是绿色了。
第一眼看到本题，会犹豫一下要怎么求取节点一到其他五个点串在一起的最短距离。
先想到最短路：图上边权最值问题，我们先考虑最短路。（确实是最普遍的（至少是我所明确的））
然后，怎么明智的使用最短路。
由于，只有五个节点。聪慧的你，肯定会第一时间想到，以五个顶点为起点，利落地都跑一遍最短路。
毕竟，不会超时。
然后，怎么去求取这五个顶点之间的最短距离呢。
现在，再想最短路如何去做，显然是不明智的选择。
只有五个顶点。全部都需要碰到。
wow。DFS全排列！
（这是因为，能够承担的其这个复杂度。）
你需要明白，题目给出数据，不是白给。
需要学会像上一题那样，分析题目的弱点。
再结合其弱点，匹配相应的武器（即算法）。
<=10 。太特殊了。
只要你有足够的DFS练习量。
几乎是一眼就能想到。
此时此刻，我们的网终于有了第一条丝线。
下一题！
糖果共享
这道题目拿到手之后就会发现小朋友们呈环状。
不过对于最短路来说，这只是边加在哪里的问题。
但是对于其他的算法。那就是需不需要断环成链的问题。
本题不难。好像就是需要加边的时候懂点手脚即可。
哈哈哈哈哈哈。“新的一天，要做被神明青睐的人。”
这其实是一个梗。来源于我们班老师说“我们班现在已经有同学被四校（上海最好的四所高中）青睐了。”而后附加了一系列的赞美。说的好像马上就要上天堂了一样。
过了。
喜欢高速打字。像是在飙车一样。
展示代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct Node{
int z;
ll q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
vector<Node>v[N];
ll dis[N];
bool vis[N];
ll t[N];//每个小朋友拿到糖果的时间
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
ll t;//每个小朋友拿到糖果的时间
cin>>t;
v[0].push_back({i,t});
}
for(int i=1;i<=n;i++){
ll p;//每个小朋友收到糖果之后，将糖果分给其他小朋友的时间
cin>>p;
if(i!=n)v[i].push_back({p,i+1});
else v[i].push_back({1,i+1});
}
for(int i=1;i<=n;i++)dis[i]=1e18;
q.push({s,0});
while(!q.empty()){
Node sum=q.top();
q.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to])q.push({to,dis[to]});
}
}
}
int q;
cin>>q;
for(int i=1;i<=q;i++){
int k;
cin>>k;
cout<<dis[k]<<'\n';
}
return 0;
}
这道题普遍做法似乎使用的是DP。
那等我说一下我最短路的做法，然后就看一下DP怎么写。
关于我怎么用最短路做的：
将老师设为起点，将所有人的传递时间视作边即可。
再跑一次最短路就过了。
分析：
这道题，并没有图的壳子。
而是一个隐藏款。那么在考场中，如何准确地识别出，这是一道最短路的题目呢？
首先看到题目的要求：最快什么时候拿到糖果。
我们一般考虑使用：DP，贪心，最短路。（以我目前的知识储备进行判定。）
看到n<=2e5。这把一般最短路。（或者反悔贪心（单凭上述两个信息进行判断，而不是根据题目全局。））
而且是Dijkstra。因为DP一般是O(n^2)时间复杂度的（据我目前所知）（虽然这题确实是O（n)时间复杂度，但是线性DP比较稀有）。
贪心，一般是O(n)的吧。它能开大数据为什么不开。
这就是 算法选择。
然后就是加边。如果我没记错的话，这个知识点应该是超级源点（应该是的）。
就是将所有点，都与点0建交。然后跑最短路。
那么。
哦。突然想起：记得开long long。
好的，接下来瓦达西去了解一下怎么用DP做。
哦。失策了。这么简单。
不应该去看题解的。应该自己想的[悲伤蛙.jpg]。
哦。也没想象中的这么简单。
先放代码喵：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long ll;
ll t[N],p[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>t[i];
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++)t[i+n]=t[i];
for(int i=1;i<=n;i++)p[i+n]=p[i];
for(int i=1;i<=n*2;i++){
dp[i]=min(t[i],dp[i-1]+p[i]);
}
int q;
cin>>q;
for(int i=1;i<=q;i++){
int k;
cin>>k;
cout<<dp[k+n]<<'\n';
}
return 0;
}
思路：
阅读题目可知，一个小朋友一共有两次拿到糖果的机会。
有帮助，赞一个