当前位置:网站首页>Flody的应用
Flody的应用
2022-07-06 04:43:00 【Zqchang】
应用
这里的最小环和spfa求负环不一样,这里是没有负环的,就是找一个环是最小值
原理
这两个一样,第一维可以直接去掉
证明:当i=k或者j=k的时候,d[i][k]或者d[k][j]是不会更新的,也就是d[k][i][k]等于d[k-1][i][k],j同理,也就是更新的时候,d[i][k]和d[k][j]不用担心被更新过,当然就可以直接用来更新,不用担心有什么变化
例题
最短路
牛的旅行
其实就是给你一堆连通块,让你加边,使得连通块成为 一个大的连通块
让你求这个大的连通块中两点之间最大值的最小值
分为两种情况,也就是途中两种,一种是原本连通块中的最大值,另一个是经过新边的最长路径
做法如下
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
#define x first
#define y second
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 155;
const double INF = 1e20;
int n;
PII q[N];
double d[N][N];
double maxd[N];
char g[N][N];
double get_dist(PII a, PII b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
signed main()
{
fast;
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;
else if(g[i][j] == '0') d[i][j] = INF;
else d[i][j] = get_dist(q[i], q[j]);
}
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 res1 = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
if(d[i][j] < INF / 2)
maxd[i] = max(maxd[i], d[i][j]);
res1 = max(res1, maxd[i]);
}
double res2 = INF;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(d[i][j] > INF / 2)
res2 = min(res2, maxd[i] + get_dist(q[i], q[j]) + maxd[j]);
printf("%.6lf\n", max(res1, res2));
return 0;
}
传递闭包
传递闭包:把所有间接能到的点,都连上边之后,就是一个原图的传递闭包(详见离散)
fioyd算法可以在O( n 3 n^3 n3)的复杂度之内,求出来原图的一个传递闭包,用邻接矩阵的形式表示的
很好做,就是给你一个邻接矩阵g[i][j],然后初始化,方式如图,然后三层循环,如果i能到k,k能到j,就让d[i][j] = 1
边栏推荐
- Yyds dry goods inventory OSI & tcp/ip
- Can Flink SQL read multiple topics at the same time. How to write in with
- How to estimate the population with samples? (mean, variance, standard deviation)
- ue5 小知识 FreezeRendering 查看视锥内渲染的物体
- P2102 floor tile laying (DFS & greed)
- Basic explanation of turtle module - draw curve
- SQL注入漏洞(MSSQL注入)
- C. The third problem
- Easyrecovery靠谱不收费的数据恢复电脑软件
- Canal synchronizes MySQL data changes to Kafka (CentOS deployment)
猜你喜欢
Sorting out the latest Android interview points in 2022 to help you easily win the offer - attached is the summary of Android intermediate and advanced interview questions in 2022
Postman前置脚本-全局变量和环境变量
coreldraw2022新版本新功能介绍cdr2022
Postman断言
Guitar Pro 8.0最详细全面的更新内容及全部功能介绍
[network] channel attention network and spatial attention network
[05-1, 05-02, 05-03] network protocol
L'introduction en bourse de MSK Electronics a pris fin: 800 millions de RMB d'actifs de Henan étaient des actionnaires
Easyrecovery reliable and toll free data recovery computer software
Postman关联
随机推荐
[network] channel attention network and spatial attention network
Word cover underline
Canal synchronizes MySQL data changes to Kafka (CentOS deployment)
Can CDC pull the Oracle table in full
[NOIP2009 普及组] 分数线划定
Finance online homework
Digital children < daily question> (Digital DP)
The web project imported the MySQL driver jar package but failed to load it into the driver
How to estimate the population with samples? (mean, variance, standard deviation)
Visio draw fan
npm命令--安装依赖包--用法/详解
Programmers' position in the Internet industry | daily anecdotes
Sorting out the latest Android interview points in 2022 to help you easily win the offer - attached is the summary of Android intermediate and advanced interview questions in 2022
力扣(LeetCode)186. 翻转字符串里的单词 II(2022.07.05)
[face recognition series] | realize automatic makeup
Can Flink SQL read multiple topics at the same time. How to write in with
Postman测试报告
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
【HBZ分享】ArrayList的增删慢查询快的原因
捷码赋能案例:专业培训、技术支撑,多措并举推动毕业生搭建智慧校园毕设系统