XP04 - day06
2026-08-17 17:10:13
发布于：广东
113阅读
0回复
0点赞
Floyd 算法笔记
1. 作用
Floyd 用来求：
任意两点之间的最短路
适合：
- 点数比较少
- 需要求所有点对之间的最短距离
- 可以处理负边
- 但不能有负环
2. 核心思想
假设现在考虑点 k 能不能作为中转点。
原本：
i --------> j
经过 k：
i ----> k ----> j
所以比较：
d[i][j]
和
d[i][k]+d[k][j]
取更小的：
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
3. 三维 DP 理解
原始状态：
f[k][i][j]
表示：
只允许
1~k作为中间点时，i -> j的最短距离。
转移：
f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])
也就是：
不经过 k
和
经过 k
取最小值
因为只需要上一层，所以可以压缩成二维数组 d[i][j]。
4. 初始化
自己到自己：
d[i][i]=0;
其他点一开始不可达：
d[i][j]=INF;
有边：
d[x][y]=min(d[x][y],w);
注意有重边，所以要取最小值。
5. Floyd 模板
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(d[i][k]!=INF&&d[k][j]!=INF){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
循环顺序必须是：
k
i
j
其中 k 表示当前允许使用的中转点。
6. 为什么能判断负环
正常情况下：
d[i][i]=0;
如果 Floyd 跑完后：
d[i][i]<0
说明从 i 出发绕一圈回到 i，总权值是负数。
所以存在负环：
for(int i=1;i<=n;i++){
if(d[i][i]<0){
cout<<-1;
return 0;
}
}
7. 小例子
有：
1 -> 2 = 3
2 -> 3 = 4
1 -> 3 = 10
原来：
d[1][3]=10
当 k=2 时：
1 -> 2 -> 3
3 + 4 = 7
所以：
d[1][3]=min(10,3+4);
得到：
d[1][3]=7
8. 复杂度
时间复杂度：
O(n^3)
空间复杂度：
O(n^2)
所以 Floyd 一般适用于：
n ≈ 500
左右的图。
一句话记忆
Floyd 就是不断枚举中转点
k，判断i -> k -> j会不会比原来的i -> j更短。
核心代码只有一句：
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
floyd算法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=510;
const ll INF=1e18;
int n,m;
ll d[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)d[i][j]=0;
else d[i][j]=INF;
}
}
for(int i=1;i<=m;i++){
int x,y;
ll w;
cin>>x>>y>>w;
d[x][y]=min(d[x][y],w);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(d[i][k]!=INF&&d[k][j]!=INF){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
//判断负环
for(int i=1;i<=n;i++){
if(d[i][i]<0){
cout<<-1;
return 0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(d[i][j]==INF)cout<<1000000000<<" ";
else cout<<d[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
判断负环
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
const int M=10010;
const int INF=0x3f3f3f3f;
struct Edge{
int a,b,c;
}edges[M];
int n,m,cnt;
int dist[N],lastd[N];
bool bellman_ford(){
for(int i=1;i<=n;i++){
dist[i]=INF;
}
dist[1]=0;
// 最多松弛n轮
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)lastd[j]=dist[j];
bool flag=false;
// 遍历每一条实际存储的边
for(int j=0;j<cnt;j++){
Edge e=edges[j];
if(lastd[e.a]<INF && dist[e.b]>lastd[e.a]+e.c){
dist[e.b]=lastd[e.a]+e.c;
flag=true;
}
}
// 本轮没有更新，说明不存在可达负环
if(!flag) return false;
// 第n轮还能更新，说明存在可达负环
if(i==n) return true;
}
}
int main(){
int t;
cin>>t;
while(t--){
cin>>n>>m;
cnt=0;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
// u -> v
edges[cnt++]={u,v,w};
// 非负边是无向边，需要加入反向边
if(w>=0){
edges[cnt++]={v,u,w};
}
}
if(bellman_ford()) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
bellman-ford
邮递员送信
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1e9;
struct Node {
int id, dist;
bool operator<(const Node& other) const {
return dist > other.dist; // 小根堆
}
};
struct Edge {
int to, w;
};
vector<Edge> g1[N], g2[N]; // 正向图、反向图
int dist1[N], dist2[N];
bool vis[N];
// 单源最短路 Dijkstra
void dijkstra(int s, int n, vector<Edge> g[], int dist[]) {
for (int i = 1; i <= n; i++) {
dist[i] = INF;
vis[i] = false;
}
priority_queue<Node> q;
dist[s] = 0;
q.push({s, 0});
while (!q.empty()) {
Node u = q.top(); q.pop();
if (vis[u.id]) continue;
vis[u.id] = true;
for (auto e : g[u.id]) {
int v = e.to, w = e.w;
if (dist[v] > dist[u.id] + w) {
dist[v] = dist[u.id] + w;
q.push({v, dist[v]});
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
g1[u].push_back({v, w}); // 正向边
g2[v].push_back({u, w}); // 反向边
}
// 起点到达 所有点的最短路
dijkstra(1, n, g1, dist1); // 1 -> i
//
dijkstra(1, n, g2, dist2); // i -> 1 (反向图)
long long ans = 0;
for (int i = 2; i <= n; i++) {
if (dist1[i] >= INF/2 || dist2[i] >= INF/2) { // 不可达
cout << -1 << '\n';
return 0;
}
ans += dist1[i] + dist2[i];
}
cout << ans << "\n";
return 0;
}
dijkstra 朴素版本
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int INF = 1e9;
struct Edge {
int to;
int w;
};
vector<Edge> tr[N];
int n, m, s;
int dist[N];
bool vis[N];
int main() {
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
// 有向边：a -> b，边权为c
tr[a].push_back({b, c});
}
for (int i = 1; i <= n; i++) {
dist[i] = INF;
}
dist[s] = 0;
// 最多确定n个节点的最短路
for (int i = 1; i <= n; i++) {
int u = -1;
// 找到未访问节点中距离最小的节点
for (int j = 1; j <= n; j++) {
if (!vis[j] &&
(u == -1 || dist[j] < dist[u])) {
u = j;
}
}
// 剩余节点均无法到达
if (u == -1 || dist[u] == INF) {
break;
}
vis[u] = true;
// 使用u更新它能到达的节点
for (Edge edge : tr[u]) {
int v = edge.to;
int w = edge.w;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) {
cout << -1 << " ";
} else {
cout << dist[i] << " ";
}
}
return 0;
}
dijkstra 堆优化 mlogn
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
struct Edge {
int to;
int w;
};
struct Node {
int id;
int dist;
bool operator<(const Node& other) const {
return dist > other.dist;
}
};
vector<Edge> tr[N];
int n, m, s;
int dist[N];
bool vis[N];
int main() {
cin >> n >> m >> s;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
tr[a].push_back({b, c});
}
for (int i = 1; i <= n; i++) {
dist[i] = 1e9;
}
priority_queue<Node> q;
dist[s] = 0;
q.push({s, 0});
while (!q.empty()) {
Node u = q.top();
q.pop();
if (vis[u.id]) continue;
vis[u.id] = true;
for (Edge x : tr[u.id]) {
int v = x.to;
int w = x.w;
if (dist[v] > dist[u.id] + w) {
dist[v] = dist[u.id] + w;
q.push({v, dist[v]});
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] == 1e9) {
cout << -1 << " ";
} else {
cout << dist[i] << " ";
}
}
return 0;
}
并查集笔记
1. 并查集是干什么的？
并查集主要解决两类问题：
- 合并两个集合
- 判断两个点是否属于同一个集合
常见题型：
有 个点，一开始互不相连。
不断进行“连边”和“询问两点是否连通”的操作。
2. 核心数组 fa[]
int fa[N];
含义：
fa[i] = i号点的父亲
一开始每个点自己就是一个集合：
for(int i=1;i<=n;i++)fa[i] = i;
例如有 5 个点：
1 2 3 4 5
↑ ↑ ↑ ↑ ↑
1 2 3 4 5
也就是：
fa[1]=1
fa[2]=2
fa[3]=3
fa[4]=4
fa[5]=5
3. 找集合的老大 find
int find(int x){
if(fa[x]!=x)return fa[x] = find(fa[x]);
return x;
}
find(x)：
找到 所在集合的根节点（老大）。
例如：
1 → 2 → 3
↑
3
此时：
fa[1]=2
fa[2]=3
fa[3]=3
所以：
find(1)
会一直向上找：
1 → 2 → 3
最终得到：
find(1)=3
4. 路径压缩
这一句非常重要：
fa[x] = find(fa[x]);
原来：
1 → 2 → 3 → 4
↑
4
执行：
find(1);
之后会变成：
1 ─┐
2 ─┼→ 4
3 ─┘
也就是以后再找根节点，可以直接找到 。
这叫：
路径压缩
作用：让后面的查询非常快。
5. 合并两个集合
先找到两个点的老大：
int fx = find(x);
int fy = find(y);
然后：
if(fx!=fy)fa[fx] = fy;
意思就是：
让 的老大认 的老大当父亲。
例如：
集合1：1 → 2
集合2：3 → 4
假设：
find(1)=2
find(3)=4
执行：
fa[2]=4;
得到：
1 → 2 → 4 ← 3
它们就变成同一个集合了。
6. 判断是否在同一个集合
if(find(x)==find(y))
cout<<"Y\n";
else
cout<<"N\n";
核心思想：
两个点的老大相同，就属于同一个集合。
例如：
1 → 3 ← 2
4 → 5
那么：
find(1)=3
find(2)=3
所以 和 连通。
但是：
find(1)=3
find(4)=5
所以 和 不连通。
7. 小例子
初始：
1 2 3 4
执行：
1 1 2
合并 ：
1 → 2
再执行：
1 2 3
合并 ：
1 → 2 → 3
询问：
2 1 3
因为：
find(1)=3
find(3)=3
所以输出：
Y
询问：
2 1 4
因为：
find(1)=3
find(4)=4
所以输出：
N
8. 模板
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int fa[N];
int find(int x){
if(fa[x]!=x)return fa[x] = find(fa[x]);
return x;
}
int main(){
int n,m;
cin>>n>>m;
// 初始化
for(int i=1;i<=n;i++)fa[i] = i;
while(m--){
int op,x,y;
cin>>op>>x>>y;
int fx = find(x);
int fy = find(y);
// 合并
if(op==1){
if(fx!=fy)fa[fx] = fy;
}
// 查询
else{
if(fx==fy)cout<<"Y\n";
else cout<<"N\n";
}
}
return 0;
}
9. 记忆口诀
fa[i]：我的爸爸是谁
find(x)：找到我的老大
fa[fx]=fy：两个帮派合并
find(x)==find(y)：是不是一个帮派
并查集最核心就三步：
// 1. 初始化
fa[i] = i;
// 2. 找老大
find(x);
// 3. 合并
fa[find(x)] = find(y);
有路径压缩后，单次操作可以近似看成 ， 次操作总体近似 。
最小生成树 kruskal
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int fa[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
struct node{
int x,y,z;
}a[N];
bool cmp(node a,node b){
return a.z<b.z;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+m+1,cmp);
long long ans = 0;
int cnt = n;//独立的
for(int i=1;i<=m;i++){
int x = a[i].x,y =a[i].y,z = a[i].z;
if(cnt==1)break;
if(find(x)!=find(y)){
fa[find(x)]=find(y);
ans+=z;
cnt--;
}
}
if(cnt==1)cout<<ans;
else cout<<"orz";
return 0;
}
全部评论 3
#include <iostream> using namespace std; constexpr int N = 2e5 + 10; long long fa[N]; long long find(int x) { if (fa[x] == x) { return x; } return fa[x] = find(fa[x]); } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { fa[i] = i; } while (m--) { int x, y, z; cin >> z >> x >> y; if (z == 1) { fa[find(x)] = fa[find(y)]; } else { if (find(x) == find(y)) { cout << 'Y'; } else { cout << 'N'; } cout << '\n'; } } return 0; }老师为什么合并的时候不能写成fa[find(x)] = fa[find(y)];？
2天前 来自 广东
0
有帮助，赞一个