Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <cmath>
- #include <iomanip>
- #include <algorithm>
- using namespace std;
- ifstream fin("spantree.in");
- ofstream fout("spantree.out");
- class vertex {
- public:
- int x;
- int y;
- };
- class Edge {
- public:
- int initial;
- int last;
- double weight;
- };
- double calcWeight(vertex initial,vertex last) {
- double weight = sqrt(pow((initial.x - last.x),2)+pow((initial.y - last.y),2));
- return weight;
- }
- int findSet(int v , int root[]) {
- if(root[v] == v)
- return v;
- return root[v] = findSet(root[v],root);
- }
- bool unite(int u, int v, int rank[],int root[]) {
- int rootU = findSet(u, root);
- int rootV = findSet(v, root);
- if(rootU != rootV) {
- if(rank[rootU] < rank[rootV])
- swap(rootU,rootV);
- root[rootV] = rootU;
- if(rank[rootU] == rank[rootV]) {
- rank[rootU]++;
- }
- return true;
- }
- return false;
- }
- double MSTweight(vertex V[],int vertices, int rank[],int root[]) {
- int edges = (vertices - 1)*(vertices)/2;
- Edge *E = new Edge[edges];
- int k = 0;
- for(int i = 0; i < vertices; i++) {
- for(int j = i + 1; j < vertices; j++) {
- double weight = calcWeight(V[i], V[j]);
- Edge e{i,j,weight};
- E[k++] = e;
- }
- }
- sort(E,E + edges,[](Edge const &a,Edge const &b)-> bool { return a.weight < b.weight;});
- double MSTweight = 0;
- for(int i = 0; i < edges; i++) {
- if(unite(E[i].initial,E[i].last,rank,root))
- MSTweight += E[i].weight;
- }
- return MSTweight;
- }
- int main() {
- int vertices,x,y;
- fin >> vertices;
- vertex V[vertices];
- int rank[vertices];
- int root[vertices];
- for(int i = 0; i < vertices; i++) {
- fin >> x >> y;
- vertex v{x,y};
- V[i] = v;
- rank[i] = 0;
- root[i] = i;
- }
- fout << fixed << setprecision(20) << MSTweight(V,vertices,rank,root);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement