企业官网建设流程全解析

【题目来源】
https://www.luogu.com.cn/problem/P2850

【题目描述】
Farmer John 在探索他的农场时发现了许多神奇的虫洞。虫洞的特性非常特殊——它是一个单向通道，能将你传送到它的目的地，而且时间还会回溯到过去！FJ 的每个农场包含 N(1≤N≤500) 块编号为 1∼N 的田地、M(1≤M≤2500) 条双向路径和 W(1≤W≤200) 个虫洞。
作为狂热的时间旅行爱好者，FJ 希望实现：从某块田地出发，经过若干路径和虫洞后，在初始离开时间之前回到起点。这样或许他能遇见自己 :)
为了判断可行性，FJ 将提供 F(1≤F≤5) 个农场的完整地图。所有路径通行耗时不超过 10,000 秒，虫洞最多能将 FJ 带回 10,000 秒前。

【输入格式】
第 1 行：一个整数 F，表示农场数。后续为 F 个农场的数据。
每个农场：
第 1 行：三个空格分隔的整数 N（田地数）, M（双向路径数）, W（虫洞数）。
第 2∼M+1 行：每行三个空格分隔的整数 (S,E,T)，表示 S 和 E 间有一条耗时 T 秒的双向路径。两块田地间可能存在多条路径。
第 M+2∼M+W+1 行：每行三个空格分隔的整数 (S,E,T)，表示一条从 S 到 E 的单向虫洞，可将 FJ 带回 T 秒前。

【输出格式】
输出 F 行：对每个农场，若 FJ 能达成目标输出YES，否则输出NO。​​​​​​​

【输入样例】
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8​​​​​​​

【输出样例】
NO
YES

【数据范围】
1≤N≤500、1≤M≤2500、1≤W≤200、1≤F≤5

【算法分析】
● 题目中 road=2500，每条存 2 条边就是 5000，再加 200 虫洞，单组最多 5200 条边。所以，代码中把 M 设为6005。否则，数组越界，直接 RE！​​​​​​​

● Bellman-Ford 算法使用边集数组存图，而非邻接表。这是因为 Bellman-Ford 在每一轮迭代中，都需要遍历图中全部边执行松弛操作，无需查询某个顶点的出边。而邻接表的核心优势，是快速获取单个顶点的邻接边，但这项能力在 Bellman-Ford 算法中完全用不到。因此，邻接表额外的索引结构自然成为冗余。反观边集数组，它仅存储每条边自身的信息，结构极简，恰好适配 Bellman-Ford 算法的执行逻辑。
● 包含 n 个顶点的图，其最短路径一定是简单路径（路径中不会重复经过同一个顶点，不含任何环），即最多包含 n-1 条边。所以，Bellman-Ford 算法最多只需要松弛 n-1 轮。
（1）算法的第 k 轮松弛，作用是求出“最多经过 k 条边”能够得到的最短距离。第 1 轮更新仅用 1 条边可达的最短路，第 2 轮更新最多 2 条边的最短路，以此类推。当完成 n-1 轮松弛后，所有简单路径对应的最短距离都已经被更新完成。
（2）如果执行完 n-1 轮之后，仍然还有边可以继续松弛，就说明图中存在“负环”。即可以不断环绕这个环，无限降低路径总权值，不存在有限的最短路径。

​​​​​​​● 本题为无向图。无向边 u-v 等价于两条方向相反的有向边：u → v 与 v → u。因此在使用 Bellman‑Ford 算法的边集数组存图时，读入一条无向边，需要同时存入这两条有向边，才能完整表达双向连通关系。

【算法代码】

#include <bits/stdc++.h> using namespace std; const int N=5e2+5; const int M=6e3+5; int dis[N]; struct edge { int u,v,w; } e[M]; int n,m; bool bellman(int n,int m) { memset(dis,0,sizeof dis); for(int i=1; i<=n; i++) { bool flag=0; for(int j=1; j<=m; j++) { int u=e[j].u, v=e[j].v, w=e[j].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; flag=1; } } if(!flag) break; } for(int j=1; j<=m; j++) { int u=e[j].u,v=e[j].v,w=e[j].w; if(dis[v]>dis[u]+w) { return true; } } return false; } int main() { int T; cin>>T; while(T--) { int farm,road,hole; cin>>farm>>road>>hole; int cnt=0; for(int i=1; i<=road; i++) { int u,v,w; cin>>u>>v>>w; e[++cnt]= {u,v,w}; e[++cnt]= {v,u,w}; } for(int i=1; i<=hole; i++) { int u,v,w; cin>>u>>v>>w; e[++cnt]= {u,v,-w}; } if(bellman(farm,cnt)) cout<<"YES\n"; else cout<<"NO\n"; } return 0; } /* in: 2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8 out: NO YES */

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/166848957