Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.78 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. struct Vertex {
  6.         int x, y, depth;
  7.     struct Vertex *parent;
  8. } **vertex;
  9.  
  10. struct Edge {
  11.     int u, v, len;
  12. } *edge;
  13.  
  14. struct Vertex* Find(struct Vertex* v) {
  15.     if(v->parent == v) return v;
  16.     else return v->parent = Find(v->parent);
  17. }
  18.  
  19. void Union(struct Vertex *u, struct Vertex *v) {
  20.     struct Vertex *rootOfU = Find(u);
  21.     struct Vertex *rootOfV = Find(v);
  22.     if(rootOfU->depth < rootOfV->depth) rootOfU->parent = rootOfV;
  23.     else rootOfV->parent = rootOfU;
  24. }
  25.  
  26. int compare(const void *u, const void *v) {
  27.     const struct Edge *a = u;
  28.     const struct Edge *b = v;
  29.     if (a->len > b->len) return 1;
  30.     else if(a->len == b->len) return 0;
  31.     return -1;
  32. }
  33.  
  34. void MST_Kruskal(int M, int N) {
  35.     qsort(edge, M, sizeof(struct Edge), compare);
  36.     int i = -1, counter = 0;
  37.     double mst = 0;
  38.     while(++i < M && counter < N - 1)
  39.         if(Find(vertex[edge[i].u]) != Find(vertex[edge[i].v])) {
  40.             mst += sqrt(edge[i].len);
  41.             Union(vertex[edge[i].u], vertex[edge[i].v]);
  42.             counter++;
  43.         }
  44.     printf("%.2f", mst);
  45. }
  46.  
  47. int main(int argc, char **argv) {
  48.     int N, M, x, y, helper = 0;
  49.     scanf("%d", &N);
  50.     M = N * (N - 1) / 2;
  51.     vertex = malloc(N * sizeof(struct Vertex*));
  52.     for(int i = 0; i < N; i++) {
  53.         scanf("%d%d", &x, &y);
  54.         vertex[i] = malloc(sizeof(struct Vertex));
  55.         vertex[i]->x = x;
  56.         vertex[i]->y = y;
  57.         vertex[i]->depth = 0;
  58.         vertex[i]->parent = vertex[i];
  59.     }
  60.     edge = malloc(M * sizeof(struct Edge));
  61.     for(int i = 0; i < N; i++) {
  62.         for(int j = i + 1; j < N; j++) {
  63.             edge[helper].u = i;
  64.             edge[helper].v = j;
  65.             edge[helper++].len = (vertex[i]->x - vertex[j]->x) * (vertex[i]->x - vertex[j]->x) + (vertex[i]->y - vertex[j]->y) * (vertex[i]->y - vertex[j]->y);
  66.         }
  67.     }
  68.     MST_Kruskal(M, N);
  69.     for(int i = 0; i < N; i++)
  70.         free(vertex[i]);
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement