Floyd算法中，如何计算传递闭包、最小环及恰好包含k条边的路径？

2026-05-22 09:102阅读0评论SEO基础

内容介绍
文章标签
相关推荐

本文共计1356个文字，预计阅读时间需要6分钟。

牛的旅行链接：https://www.acwing.com/problem/content/1127/求两个连通块连接后最大直连度（可能是连接之前的直连度，也可能是连接之后的最大值）。

1. 如果能达到连接两个点的距离 + 建图

2.建图后floyd

3.取dm

牛的旅行www.acwing.com/problem/content/1127/

求两个连通块连接后最大直径 (可能是连接之前的直径，可能是连接之后的最大值)
1.如果能到达连接两个点的距离建图
2.建图后floyd
3.取dmin

#include <cstring> #include <iostream> #include <algorithm> #include <cmath> #define x first #define y second using namespace std; typedef pair<double, double> PDD; const int N = 155; const double INF = 1e20; int n; PDD q[N]; double d[N][N]; double maxd[N]; char g[N][N]; double get_dist(PDD a, PDD b) { double dx = a.x - b.x; double dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } int main() { cin >> n; for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;//输入点对的横纵坐标 for (int i = 0; i < n; i ++ ) cin >> g[i];//存领接矩阵 for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) if (i == j) d[i][j] = 0;//到自己距离为0 else if (g[i][j] == '1') d[i][j] = get_dist(q[i], q[j]);//发现如果能“直接”走到的话，计算点的距离 else d[i][j] = INF;//如果不能走到距离设置为正无穷 for (int k = 0; k < n; k ++ ) for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);//做一遍的佛洛依德计算“间接”两点的最短路 double r1 = 0; for (int i = 0; i < n; i ++ ) { for (int j = 0; j < n; j ++ ) if (d[i][j] < INF / 2)//说明i走到的j maxd[i] = max(maxd[i], d[i][j]);//如果走不到求maxd i存i能走到的点的最大值 r1 = max(r1, maxd[i]);//r1存某个连通块的最大值 } double r2 = INF; for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) if (d[i][j] > INF / 2)//如果不能走到 r2 = min(r2, maxd[i] + maxd[j] + get_dist(q[i], q[j]));//计算不能走到的最小值也就是两个连通块的最小值 printf("%.6lf\n", max(r1, r2)); return 0; } 排序www.acwing.com/problem/content/345/

求传递背包给出若干按个关系问是否根据这些关系给出对应的顺序
可以top()排序
排序后，排序数组不为n个，则表示有环，矛盾，跳出循环
排序后，排序数组为n个，但是在过程中，有2个或以上的点在队列中，表示拓扑序并不唯一，那么此时并不能确定所有点的顺序，因此进行下一次循环
排序后，排序数组为n个，且在过程中，队列中一直只有一个，拓扑序唯一，输出结果，跳出循环

floyd

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 26; int n, m; bool d[N][N]; bool st[N]; void floyd() //通过floyd来逐渐更新每两个点的连通情况 { for(int k = 0; k < n; k ++) for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) d[i][j] |= d[i][k] & d[k][j]; //if(!d[i][j]) d[i][j] = d[i][k] & d[k][j];是错误的 //如果原来是 i->k k->j 通过这样让i->j 同时如果本来i->j也一定要i->j } int check() { for(int i = 0; i < n; i ++) //矛盾情况发现自己能到达自己 if(d[i][i]) return 2; for(int i = 0; i < n; i ++) //不能确定情况 for(int j = 0; j < i; j ++) if(!d[i][j] && !d[j][i]) return 0;//发现不能互相到达 return 1; } char get_min() //每次取出最小的值用于输出大小关系 { for(int i = 0; i < n; i ++) if(!st[i]) //如果当前这个数没有取出 { bool flag = true; for(int j = 0; j < n; j ++)//判断是否最小 if(!st[j] && d[j][i])//如果有点比他更小的就要推出 { flag = false; break; } if(flag) { st[i] = true;//没有更小的那就是这个了 return 'A' + i; } } } int main() { while(cin >> n >> m, n || m) { memset(d, 0, sizeof d); int type = 0, t; // t 记录轮次 type记录判断出来与否的标志 for(int i = 1; i <= m; i ++) { char str[5]; cin >> str; int a = str[0] - 'A', b = str[2] - 'A'; //获得两个关系 if(!type)//如果还没确定下来 { g[a][b] = 1;//a小于b 连接一条边 floyd();//每次连接做一次floyd type = check();//检查下加入这次后的情况 if(type) t = i;//t找到是哪个关系 } } if(!type) puts("Sorted sequence cannot be determined."); else if(type == 2) printf("Inconsistency found after %d relations.\n", t); else { memset(st, 0, sizeof st); printf("Sorted sequence determined after %d relations: ", t); for(int i = 0; i < n; i ++) printf("%c", get_min()); printf(".\n"); } } return 0; } 观光之旅

求最小环
和以前的题不同这里是去掉某个环的某点来判断的
因为对于 i-j-k-i 这个环如果想要去掉去掉k这个点剩下的d[i][j]一定是最短的(满足dp) 所以d[i][j]+g[k][j]+g[j][i]

1.本题的思路就是考虑最小环里面节点编号最大的节点为k,且环里面与k相连的两个点为i，j，环的长度为g[i][k]+g[k][j]+d[j][i]；
2.则d[j][i]则表示j到i且经过的节点编号小于k,因为在环中k就是最大的，只能经过小于k的节点了;
3.则这与floyd中k次循环开始前的d[i][j]意义相同;
4.那就不妨在floyd的第一重循环就求一下以k为最大节点编号的环的长度，美滋滋

标签：Floyd 求传递闭包 top