算法的网 2（持续更新）
2026-04-11 16:20:10
发布于：上海
观前须知：
1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意。
2.每一句话的基础是作者浅薄的知识储备。如果你认为我讲的不对，欢迎指正。但是请友好用语。因为作者心理素质奇差无比。
————————————————————————————————————————
在@Xylophone的帮助下。原始人成功学习加入了latex。获得成就：更加好看的帖子。
————————————————————————————————————————
这是我们的网现在的样子：
书接上集。
一个小朋友有两次拿到糖果的机会。
一次是从老师那里，一次是从旁边的人那里。
那么其实可以直接推出状态转移方程：
(t和p的定义都与题目相同）
老师那里的时间是固定的。要考虑的就是同学那里。
要考虑什么呢？
环。
已知小朋友坐成一圈。
那么就用到最经典的方法：段环成链。
OK。
就这样，黄体门槛。
我们可以总结一下：
由于这道题目可以用最短路也可以用DP。
初步的结论就是，它们都是可以用来求最值的。
（第二个结论是硬推的，真正碰到应该会比较少吧）
第二个结论就是当需要求取到很多个点的最小值，而且这个点的来源比较有限（比如只能够从左边来右边来）。那它就既可以是DP（有概率）又可以是最短路。不过最短路的范围更广，它比要求来源。
关于DP为何会要求来源：因为时间复杂度的问题，不限制来源那就是FLOYD了。
下一题吧喵。
Alias
手气不太好……这好像是个模板。
等我看看（今天做完黄题，明天就开最短路绿了）
好像是全源最短路叭。
哦。好像还是有点特殊的。点是字符串欸。
所以手气还行。
这题的思路是用map存一下字符串对应的点的标号即可。
然后就是最短路模板。
上代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
typedef long long ll;
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];
map<string,int>mp;
int now=0;
string a[N];
ll l[N][N];//记录
void solve(int x){
for(int i=1;i<=now;i++)dis[i]=1e18,vis[i]=0;
dis[x]=0;
pq.push({x,0});
while(!pq.empty()){
Node sum=pq.top();
pq.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;
ll 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<=now;i++)l[x][i]=dis[i];
return;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
string x,y;
ll t;
cin>>x>>y>>t;
if(mp[x]==0)a[++now]=x,mp[x]=now;
if(mp[y]==0)a[++now]=y,mp[y]=now;
v[mp[x]].push_back({mp[y],t});
}
for(int i=1;i<=now;i++)solve(i);
int q;
cin>>q;
for(int i=1;i<=q;i++){
string x,y;
cin>>x>>y;
if(l[mp[x]][mp[y]]!=1e18)cout<<l[mp[x]][mp[y]]<<'\n';
else cout<<"Roger\n";
}
return 0;
}
思路分析：
本题是STL和最短路的一个轻微结合。
大致需要点一点的就是：如果有string代替数字，那么可以用map存完再整。
下一题吧。
城市规划
模板题。
不过是BFS。可以多连一条线。
先把dijkstra的模板放一下（然后放BFS做法）：
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v[N];
int dis[N];
bool vis[N];
priority_queue<Node>q;
int ans=INT_MAX;
int ta=0;
void solve(int x){
for(int i=1;i<=n;i++)dis[i]=INT_MAX;
for(int i=1;i<=n;i++)vis[i]=0;
dis[x]=0;
q.push({x,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 sum=0;
for(int i=1;i<=n;i++)sum=max(sum,dis[i]);
if(sum<ans){
ans=sum;
ta=x;
}
return;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back({y,1});
v[y].push_back({x,1});
}
for(int i=1;i<=n;i++)solve(i);
cout<<ans;
return 0;
}
这是BFS的那份代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,m;
vector<int>v[N];
int dis[N],vis[N];
queue<int>q;
int ans=INT_MAX;
int ta=0;
void solve(int x){
for(int i=1;i<=n;i++)dis[i]=INT_MAX;
dis[x]=0;
q.push(x);
int sum=0;
while(!q.empty()){
int k=q.front();
q.pop();
for(int i=0;i<v[k].size();i++){
int to=v[k][i];
if(dis[to]>dis[k]+1){
dis[to]=dis[k]+1;
sum=max(sum,dis[to]);
q.push(to);
}
}
}
if(sum<ans){
ans=sum;
ta=x;
}
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++)solve(i);
cout<<ta;
return 0;
}
唔。周一到周四实录必须大于2.5h.周五实录必须大于5h.无课程时周六必须大于8h.其他时间再定。
BFS的代码时间复杂度会比用dijkstra的时间复杂度低很多。
通过本题，我们可以发现：如果说每条边的边长都相等。那么时间复杂度为 的dijkstra就可以变成时间复杂度为的BFS。
它们本质上是同一种东西吧。这样说可能不太准确。应该说：它们本质上是在同一个框架下的。
接下来是绿题时代。大概会做十题绿。再开lca。
道路选择
问。两点之间的最短路径共有多少条。
唔……想了想，最短路的绿题还是不要定量了。做到做绿题想做黄题一样简单好了。至少十题吧。
不对啊……这题好奇怪啊。
你们好啊。我回来了。上一句话是三天前写的。
猜猜主播这三天干什么去了？当然是去摆烂了啊
骗你的。其实我生病了。
心怀繁星且步履无杂的人总是会抵达理想彼岸的。
哈哈哈哈哈哈哈。我服了。我调了三个小时。我再也不想调了。
唔。先看下一题吧。这题有点难弄。想太多天了。
通往奥格瑞玛的道路
这道题它的难点在于：它既要查询城市收费最大值中的最小值。还要确保血量不超过。
它是一个查询题目。查询最小值。
初遇这种题目你很容易会被误导。认为最短路的应该是城市收费。毕竟比较明确的提到了最值。
但实际上，它是一道用二分的题目。
二分，将查询变成判定的算法。
一般情况下，出现这几个特征的时候，可以考虑用二分
- n<=1e4（这个稍微范围大一点，看你二分里面的check要用多少时间复杂度）
2.有判定条件 （check ) 是这样的：它一般是要求一个最大值/最小值，然后需要满足一个条件
3.查询有范围（这个一般都有）
放代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
typedef long long ll;
int n,m;
struct Node{
int z;
ll q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v[N];
priority_queue<Node>pq;
ll dis[N];
bool vis[N];
int b,f[N];//经过第i个城市，需要缴费f[i]元
bool check(int x){
//边权限制
for(int i=1;i<=n;i++){
dis[i]=INT_MAX;
vis[i]=0;
}
while(!pq.empty())pq.pop();
if(f[1]>x)return 0;
dis[1]=0;
pq.push({1,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(k==n&&dis[k]<=b)return 1;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
ll len=v[k][i].q;
if(f[to]>x)continue;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to]){
pq.push({to,dis[to]});
}
}
}
}
return 0;
}
int main(){
cin>>n>>m>>b;
int l=INT_MAX,r=0;
for(int i=1;i<=n;i++){
cin>>f[i];
l=min(l,f[i]);
r=max(r,f[i]);
}
for(int i=1;i<=m;i++){
int x,y;
ll c;
cin>>x>>y>>c;
//双向边
v[x].push_back({y,c});
v[y].push_back({x,c});
}
int ans=INT_MAX;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
//那就是还可以更小
ans=min(ans,mid);
r=mid-1;
}else l=mid+1;
}
if(ans==INT_MAX)cout<<"AFK";
else cout<<ans;
return 0;
}
一行一行的代码，是我通往理想国的道路啊。
“爱就爱了，不怕没来过。”
我放一下要做的绿：
牛的旅行
社交网络
道路选择
物流网络
Lilypad Pond G
逃离僵尸岛
最长距离
黑暗城堡
旅游巴士
陌路寻诗礼
飞行路线
差分约束
下一题是
物流网络
唔。这道题的思路是把每条边都免除一遍试试看。
是枚举啊。
就这个点，想通了这个点的话，这题就没什么难度了。
放一下代码吧喵：
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
typedef long long ll;
struct yyy{
int uu,vv,ww,bb;//从城市uu到vv有一条运输费用为ww,景观评分为bb
//的道路
}node[N];
struct Node{
int z;
ll q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
int n,m;
vector<yy>v[N];
ll dis[N];
bool vis[N];
priority_queue<Node>pq;
ll ans=1e18;
void solve(int x){
for(int i=1;i<=n;i++){
dis[i]=1e18;
vis[i]=0;
}
dis[1]=0;
pq.push({1,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int a=v[k][i].uu;
int b=v[k][i].vv;
int c=v[k][i].ww;
int d=v[k][i].bb;
if(a==node[i].uu&&b==node[i].vv&&c==node[i].ww&&d==node[i].bb)c=0;
if(a==node[i].vv&&b==node[i].uu&&c==node[i].ww&&d==node[i].bb)c=0;
if(d>node[i].bb)continue;
if(dis[b]>dis[k]+c){
dis[b]=dis[k]+c;
pq.push({b,dis[b]});
}
}
}
ans=min(ans,dis[n]);
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>node[i].uu>>node[i].vv>>node[i].ww>>node[i].bb;
v[node[i].uu].push_back({node[i].vv,node[i].ww,node[i].bb});
v[node[i].vv].push_back({node[i].uu,node[i].ww,node[i].bb});
}
for(int i=1;i<=m;i++){
solve(i);//免除了第i条路经的运输费用
}
if(ans==1e18)cout<<-1;
else cout<<ans;
return 0;
}
分析：
这是一道枚举和最短路相结合的题目。
一开始写的时候，你很容易会想出一些乱搞的做法。
而不是枚举每条边免费的时候的最短路情况。
我在七级考场上，好像是用了全排列枚举+剪枝。
因为考场上有子任务。
关于如何想到正解：
看到一道比较难的题目，我时常会想：我去。这做法……是天上掉下来的吗。我在考场上遇到这样的题目，绝对想不出来。
这就是海量刷题的意义吧。总结。
（个人认为）想要在考场上遇到一道和你之前的练习完全搭不上的题目做出正解的概率为0%
那么我们来总结一下这个题目吧。
它在模板最短路里加的条件是：景观评分最高的那条路不用花钱。
也就是可以免除一条边的花销（我还看过一个和免边有关系的算法。好像是叫多层图，到时候会做这个相关的题目）
那么当这种情况出现且 的时候。我们可以考虑直接枚举。因为复杂度允许。
全部评论 6
骗你的。其实我生病了。
在长时间十二点睡六点起之后。
我的身体。诡异地病倒了。
这不科学。
这不科学。
我每天跑2公里。
喝1.5升水。心怀繁星且步履无杂的人总是会抵达理想彼岸的。
这个是不是该放个人记录里
2026-04-05 来自 广东
0观前须知：
1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意哈哈。理论上而言是的。不过总体是学习讨论。可以忽略。
2026-04-05 来自 上海
0
这城市规划还以为是 [SDOI2010] 城市规划 [SDOI2013] 城市规划 [THUWC 2018] 城市规划 [集训队作业2013] 城市规划 吓哭了
2026-04-04 来自 广东
0应该没有吧。我不会。但是我可以学。不过应该不在这里。要是我新学的算法，我应该发的是学习笔记不是算法的网。网上的算法基本都是在我有一定掌握度的情况下才能连接到一起的。
2026-04-04 来自 上海
0
有帮助，赞一个