Advertisement
Fronzilla

kruskal fallado

Oct 15th, 2017
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. struct arista
  9. {
  10.     int desde, hacia, c;
  11.     arista(int _desde, int _hacia, int _c)
  12.     {
  13.         desde = _desde;
  14.         hacia = _hacia;
  15.         c = _c;
  16.     }
  17. };
  18.  
  19. struct infoA
  20. {
  21.     int x, y;
  22.     infoA(int _x, int _y)
  23.     {
  24.         x = _x;
  25.         y = _y;
  26.     }
  27. };
  28.  
  29. bool m(const arista &a, const arista &b)
  30. {
  31.     return (a.c < b.c);
  32. }
  33. struct grafo
  34. {
  35.     vector <infoA> ifarol;
  36.     vector <int> idcomp;
  37.     vector < vector <int> > comp;
  38.     vector <arista> aristas;
  39.     vector < vector <int> > grafoF;
  40.     int n, cable = 0;
  41.  
  42.     void entrada()
  43.     {
  44.         cin >> n;
  45.         idcomp.resize(n+1);
  46.         comp.resize(n+1);
  47.         aristas.resize(n+1);
  48.         grafoF.resize(n+1);
  49.         for(int i = 0; i < idcomp.size(); i++)
  50.             idcomp[i] = i;
  51.  
  52.         ifarol.push_back(infoA(0,0));
  53.         int f, x, y;
  54.         for(int i = 0; i < n; i++)
  55.         {
  56.             cin >> f, x, y;
  57.             ifarol.push_back(infoA(x,y));
  58.         }
  59.  
  60.         for(int i = 0; i <= n; i++)
  61.         {
  62.             int x1 = ifarol[i].x;
  63.             int y1 = ifarol[i].y;
  64.             for(int j = 0; j<= n;j++)
  65.             {
  66.                 int x2 = ifarol[j].x;
  67.                 int y2 = ifarol[j].y;
  68.                 int c = sqrt(pow(y1-y2,2)+pow(x1-x2,2)) + 2;
  69.  
  70.                 if(i != j)
  71.                     aristas.push_back(arista(i,j,c));
  72.             }
  73.         }
  74.     }
  75.  
  76.     void kruskal()
  77.     {
  78.         sort(aristas.begin(),aristas.end(),m);
  79.         for(int i = 0;i < aristas.size(); i++)
  80.         {
  81.             if(esArbol(aristas[i]))
  82.             {
  83.                 add(aristas[i]);
  84.                 save(aristas[i]);
  85.             }
  86.         }
  87.  
  88.         cout << cable << endl;
  89.         for(int i = 1; i < grafoF.size(); i++)
  90.         {
  91.             cout << i << " ";
  92.             for(int j = 0; j < grafoF[i].size(); j++)
  93.             {
  94.                 cout << grafoF[i][j] << " ";
  95.             }
  96.             cout << endl;
  97.         }
  98.     }
  99.  
  100.     bool esArbol(arista a)
  101.     {
  102.         int n1 = a.desde;
  103.         int n2 = a.hacia;
  104.  
  105.         int c1 = idcomp[n1];
  106.         int c2 = idcomp[n2];
  107.  
  108.         return (c1 != c2);
  109.     }
  110.  
  111.     void add(arista a)
  112.     {
  113.         int n1 = a.desde, n2 = a.hacia;
  114.         int c1 = idcomp[n1], c2 = idcomp[n2];
  115.         int t1 = comp[c1].size();
  116.         int t2 = comp[c2].size();
  117.  
  118.         if(t1 > t2)
  119.         {
  120.             swap(n1,n2);
  121.             swap(c1,c2);
  122.             swap(t1,t2);
  123.         }
  124.  
  125.         for(int i = 0; i < t1; i++)
  126.         {
  127.             int n = comp[c1][i];
  128.             idcomp[n] = c2;
  129.             comp[c2].push_back(n);
  130.         }
  131.     }
  132.  
  133.     void save (arista a)
  134.     {
  135.         cable += a.c;
  136.         grafoF[a.desde].push_back(a.hacia);
  137.         grafoF[a.hacia].push_back(a.desde);
  138.     }
  139. };
  140. int main()
  141. {
  142.     grafo g;
  143.     g.entrada();
  144.     g.kruskal();
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement