Advertisement
Guest User

Untitled

a guest
Mar 19th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.74 KB | None | 0 0
  1. //
  2. // Created by alexey on 16.03.18.
  3. //
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define sqr(x) ((x) * (x))
  11.  
  12. using namespace std;
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15. typedef pair<int, int> PII;
  16. typedef pair<ull, ull> PULL;
  17. typedef vector<int> VI;
  18. typedef long double ld;
  19. typedef unsigned uint;
  20.  
  21. const int inf = INT_MAX;
  22. const ll linf = LLONG_MAX;
  23. const int mod = 1000007;
  24.  
  25. inline int sign(ll val) { return val > 0 ? 1 : val == 0 ? 0 : -1; }
  26. inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
  27. inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
  28. inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
  29.  
  30. struct Vertex{
  31.     double x, y;
  32.     //vector < pair <int, int> > incidence;
  33.     Vertex *parent;
  34.     int i, depth;
  35. };
  36.  
  37. struct Rib{
  38.     double length;
  39.     Vertex *v, *u;
  40.     int index;
  41. };
  42.  
  43. struct PriorityQueue{
  44.     Rib **heap;
  45.     int cap, count;
  46. };
  47.  
  48.  
  49. void MakeSet(Vertex *t){
  50.     t->parent = t;
  51. }
  52.  
  53. Vertex *Find(Vertex *x){
  54.     if(x->parent == x)
  55.         return x;
  56.     else
  57.         return x->parent = Find(x->parent);
  58. }
  59.  
  60. void Union(Vertex *x, Vertex *y){
  61.     Vertex *rootX = Find(x), *rootY = Find(y);
  62.     if(rootX->depth < rootY->depth)
  63.         rootX->parent = rootY;
  64.     else{
  65.         rootY->parent = rootX;
  66.         if(rootX->depth = rootY->depth && rootY != rootX)
  67.             rootX->depth++;
  68.     }
  69. }
  70.  
  71. void swap(PriorityQueue *Q, int i, int j){
  72.     Rib *t = Q->heap[i];
  73.     Q->heap[i] = Q->heap[j];
  74.     Q->heap[j] = t;
  75. }
  76.  
  77. bool QueueEmpty(PriorityQueue *Q){
  78.     return Q->count == 0;
  79. }
  80.  
  81.  
  82. int Insert(PriorityQueue *Q, Rib *X){
  83.     int i = Q->count;
  84.     Q->count=i+1;
  85.     Q->heap[i] = X;
  86.     while(i > 0 && (Q->heap[(i-1)/2]->length > Q->heap[i]->length)){
  87.         swap(Q, (i-1)/2, i);
  88.         i = (i-1)/2;
  89.     }
  90. }
  91.  
  92. void Heapify(int i, int n, PriorityQueue *Q){
  93.     int j = i;
  94.     while(1){
  95.         int l = 2*i +1;
  96.         int r = l+1;
  97.         j = i;
  98.         if(l<n && Q->heap[i]->length > Q->heap[l]->length) i = l;
  99.         if(r<n && Q->heap[i]->length > Q->heap[r]->length) i = r;
  100.         if(i==j)break;
  101.         swap(Q, i, j);
  102.     }
  103. }
  104.  
  105.  
  106. Rib *ExtractMin(PriorityQueue *Q){
  107.     Rib *X = Q->heap[0];
  108.     Q->count--;
  109.     if(Q->count>0){
  110.         Q->heap[0]=Q->heap[Q->count];
  111.         Heapify(0, Q->count, Q);
  112.     }
  113.     return X;
  114. }
  115.  
  116. void InitPriorityQueue(PriorityQueue *Q, int N)
  117. {
  118.     Q->heap = (Rib**)malloc(N*sizeof(Rib*));
  119.     Q->cap = N;
  120.     Q->count = 0;
  121. }
  122.  
  123. double SpanningTree(vector <Vertex> *V, PriorityQueue *Q){
  124.     int n = V->size();
  125.     double acc = 0;
  126.     int i = 0, k = 0;
  127.  
  128.     while(k < n - 1){
  129.         Rib *e = ExtractMin(Q);
  130.         if(Find(e->u)->i != Find(e->v)->i){
  131.             k++;
  132.             acc += e->length;
  133.             Union(e->u, e->v);
  134.         }
  135.         i++;
  136.     }
  137.     free(Q->heap);
  138.     return acc;
  139. }
  140.  
  141. double MST_Kruskal(vector <Vertex> *V){
  142.     int n = V->size();
  143.     PriorityQueue Q;
  144.     InitPriorityQueue(&Q, n*(n-1)/2);
  145.     for(int i = 0; i < n; i++){
  146.         for(int j = i + 1; j < n; j++){
  147.             Rib *t = (Rib*)malloc(sizeof(Rib));
  148.             t->length = sqrt(((*V)[i].x - (*V)[j].x)*((*V)[i].x - (*V)[j].x) + ((*V)[i].y - (*V)[j].y)*((*V)[i].y - (*V)[j].y));
  149.             t->v = &((*V)[i]);
  150.             t->u = &((*V)[j]);
  151.             Insert(&Q, t);
  152.         }
  153.     }
  154.     return SpanningTree(V, &Q);
  155. }
  156.  
  157.  
  158. int main(){
  159.  
  160.     int n;
  161.     cin >> n;
  162.     vector <Vertex> V(n);
  163.  
  164.     double x, y;
  165.     for(int i = 0; i < n; i++) {
  166.         V[i].i = i;
  167.         cin >> x >> y;
  168.         V[i].x = x;
  169.         V[i].y = y;
  170.         MakeSet(&V[i]);
  171.     }
  172.  
  173.     cout << fixed << setprecision(2) << MST_Kruskal(&V);
  174.  
  175.     return 0;
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement