Lecture
Gomel City Olympiad, 1999
Timur and his friends, having arrived at their old summer cottages in the summer, decided to arrange a game for the duration of their holiday. They organized a team to secretly help the villagers in their daily affairs. The holiday village is quite large, and the houses where Timur's friends live are located far from each other. How to quickly send each other messages? How to collect the guys on the board?
Timur decided to build a rope telegraph, which would connect all the houses in which the guys from his team live. There are a total of houses N. According to the map, the guys calculated the coordinates of each house (Xi, Yi) in whole numbers and wrote them out on paper. For the unit of measurement of coordinates, they took one meter. However, the question arose: which houses should be connected with a rope telegraph, so that the connection was between all the houses (perhaps through other houses), and the total length of all the ropes was as small as possible?
It is required to write a program that, according to the coordinates of the houses, would determine what is the minimum total length of all the ropes connecting all the houses to each other (possibly through other houses).
Entry order Output order N X.xx X1 Y1 X2 Y2 .. .. Xnyn
where X.xx is the minimum total length of the rope with an accuracy of two characters in the fractional part.
Input Example Output Example 5 623.61 100 200 200 200 300 400 400 200 400 100
Limitations:
0
Consider timurovts houses as the vertices of the graph, the ropes between them as the edges of the graph, and the lengths of the ropes as the weights of the edges. Now we face the problem of a minimum spanning tree.
In this case, the original graph is complete, that is, there is an edge between any two of its vertices, since according to the conditions of the problem the rope can be stretched between any two houses. In this problem, it is convenient to represent the graph as a matrix of edge weights: D [i, j] is the distance between vertices i and j.
The result of the algorithm for constructing a spanning tree using the Prima method will be represented as an array of Prev [0..N-1]: Prev [i] = j, that is, the ancestor of the vertex i in the core graph will be the vertex j, or, in other words, the minimum spanning tree will contain an edge (i, j). Vertex 0 will not have an ancestor (Pred [0] = -1).
Telegraph ()
1. Read the coordinates of houses from a file.
2. Find the distances between all pairs of houses and record the results in
adjacency matrix.
3. Use the Prima algorithm to find the smallest skeleton tree.
(to implement paragraphs 3.1-3.4):
3.1. Add all vertices to the queue and initialize the key value
infinity.
3.2. Assign key value 0 to the starting vertex.
3.3. While there are vertices in the queue, repeat paragraphs. 3.3.1-3.3:
3.3.1. Find a vertex with a minimum key.
3.3.2. Remove found vertex from the queue.
3.3.3. Update key for all incident vertices that
are in line.
3.4. Find the sum of the keys of all the vertices.
4. Print the amount of keys.
#include
#include
#include
#include
#include
using namespace std;
#define MAXVERTEXES 101 //maximal amount of vertaxes
int infinity=2000000; //infinity
float a[MAXVERTEXES][MAXVERTEXES]; //adjacency matrix (distances between houses)
int amount; //amount of houses
struct houses { //structure with coordinates o house
int x;
int y;
};
houses house[100]; //array of houses
void input(); //read coordinates of houses
void createMatrix();//find distances between houses
float prim(int); //find the minimal tree
//===================================== Main program ===============================
void main(){
input(); //read coordinates of houses
createMatrix();//find distances between houses
float length=prim(0); //length of all edges of the MST
printf("\n%0.2f\n\n",length);
//cout<<"\nThe total length of MST is "<
Comments
To leave a comment
Algorithms
Terms: Algorithms