Application of Flody

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$) 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