当前位置:网站首页>Application of Flody
Application of Flody
2022-07-06 04:47:00 【Zqchang】
List of articles
application
The smallest ring here and spfa Finding negative rings is different , There is no negative ring here , Is to find a ring that is the minimum
principle
These two are the same , The first dimension can be removed directly
prove : When i=k perhaps j=k When ,d[i][k] perhaps d[k][j] It won't be updated , That is to say d[k][i][k] be equal to d[k-1][i][k],j Empathy , That is, when updating ,d[i][k] and d[k][j] Don't worry about being updated , Of course, it can be directly used to update , Don't worry about any changes
Example
shortest path
The journey of cattle
In fact, it is to give you a bunch of connecting blocks , Let you add side , Make the connected block become A large connected block
Let you find the minimum of the maximum value between two points in this large connected block
There are two cases , In other words, there are two kinds on the way , One is the maximum value in the original connected block , The other is the longest path through the new edge
Doing this
#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;
}
Pass closures
Pass closures : Put all indirectly accessible points , Even after the top , Is a transitive closure of the original graph ( See discrete for details )
fioyd The algorithm can be used in O( n 3 n^3 n3) Within the complexity of , Find a transitive closure of the original graph , Expressed in the form of adjacency matrix
Well done , Is to give you an adjacency matrix g[i][j], Then initialize , The method is shown in the figure , Then three layers of circulation , If i Can I get to k,k Can I get to j, let d[i][j] = 1
边栏推荐
猜你喜欢
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
Canal synchronizes MySQL data changes to Kafka (CentOS deployment)
二叉树基本知识和例题
Database - MySQL storage engine (deadlock)
【LGR-109】洛谷 5 月月赛 II & Windy Round 6
Delete subsequence < daily question >
几种RS485隔离通讯的方案介绍
MPLS experiment
coreldraw2022新版本新功能介绍cdr2022
Basic explanation of turtle module - draw curve
随机推荐
[buuctf.reverse] 159_[watevrCTF 2019]Watshell
行业专网对比公网,优势在哪儿?能满足什么特定要求?
Summary of redis AOF and RDB knowledge points
Excellent PM must experience these three levels of transformation!
Platformio create libopencm3 + FreeRTOS project
[Chongqing Guangdong education] Suzhou University English film and Television Appreciation reference materials
npm命令--安装依赖包--用法/详解
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
Digital children < daily question> (Digital DP)
ETCD数据库源码分析——etcdserver bootstrap初始化存储
Weng Kai C language third week 3.1 punch in
Use sentinel to interface locally
[mathematical modeling] differential equation -- sustainable development of fishing industry
Why does MySQL need two-phase commit
[Chongqing Guangdong education] engineering fluid mechanics reference materials of southwestjiaotonguniversity
canal同步mysql数据变化到kafka(centos部署)
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
比尔·盖茨晒18岁个人简历,48年前期望年薪1.2万美元
SQL injection vulnerability (MSSQL injection)
2021 RoboCom 世界机器人开发者大赛-本科组(复赛)