[learning notes] shortest path + spanning tree

Difficult subject

Opening Portals

Good question ！

We call the portal the key point .

Let the distance between any two keys be dist(i,j) , Considering the nature of the transmission , All you need is a spanning tree that connects all the key points , And then traverse from any key point , Exactly the sum of the edge weights of the spanning tree .（ It's a little twisted ）

If we start at each key point dijkstra , The time complexity is $O(n^2\log n)$ .

For this model , We have a Multi source shortest path Algorithm ：

1. Start with each key , Find the shortest distance to each point
2. Consider enumerating an edge (u,v,w) , Connect the two keys closest to the two endpoints of this edge ：（ It is equivalent to enumerating transit points ）

The correctness is obvious .

Specially ,MST That is, every point is a key point .

Of course , An edge may be computed multiple times on the spanning tree .

Complete the MST

This problem does not require a sophisticated algorithm . Direct recklessness

You can run the complete graph directly MST , Then find a small spanning tree （ Just discuss it separately ） .

Jumping Around

boruvka Board questions

Trial for Chief

What a delicate little structure ！

I never thought it was the shortest circuit ！

Consider from (i,j) set out , The distance between adjacent grids with different colors is 1 , The distance between grids with the same color is 0 , Find the farthest black grid , The answer for dist+1 .（ Special judgment: all white ）

Consider its meaning . Equivalent to alternating black and white , Operate greedily .

Flights

Cuckoo ...

Difference constraint + shortest path ！！

Capitalism

Wonderful topic ！

First, it is judged that the odd ring must have no solution .

The picture of this problem is very special , Because it's a two-way side , Therefore, starting from any point of the connected block, you can reach other points . So let's enumerate S As a starting point , Run differential constraint .

What happens is that there will be no edge connected dis[u]=dis[v] The situation of , Otherwise, odd rings will appear .

In this way, we can get the solution of a combination method .

Then, the maximum range must be satisfied .

Cannot build super origin .qwq