Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <math.h>
- #include <algorithm>
- using namespace std;
- struct arista
- {
- int desde, hacia, c;
- arista(int _desde, int _hacia, int _c)
- {
- desde = _desde;
- hacia = _hacia;
- c = _c;
- }
- };
- struct infoA
- {
- int x, y;
- infoA(int _x, int _y)
- {
- x = _x;
- y = _y;
- }
- };
- bool m(const arista &a, const arista &b)
- {
- return (a.c < b.c);
- }
- struct grafo
- {
- vector <infoA> ifarol;
- vector <int> idcomp;
- vector < vector <int> > comp;
- vector <arista> aristas;
- vector < vector <int> > grafoF;
- int n, cable = 0;
- void entrada()
- {
- cin >> n;
- idcomp.resize(n+1);
- comp.resize(n+1);
- aristas.resize(n+1);
- grafoF.resize(n+1);
- for(int i = 0; i < idcomp.size(); i++)
- idcomp[i] = i;
- ifarol.push_back(infoA(0,0));
- int f, x, y;
- for(int i = 0; i < n; i++)
- {
- cin >> f, x, y;
- ifarol.push_back(infoA(x,y));
- }
- for(int i = 0; i <= n; i++)
- {
- int x1 = ifarol[i].x;
- int y1 = ifarol[i].y;
- for(int j = 0; j<= n;j++)
- {
- int x2 = ifarol[j].x;
- int y2 = ifarol[j].y;
- int c = sqrt(pow(y1-y2,2)+pow(x1-x2,2)) + 2;
- if(i != j)
- aristas.push_back(arista(i,j,c));
- }
- }
- }
- void kruskal()
- {
- sort(aristas.begin(),aristas.end(),m);
- for(int i = 0;i < aristas.size(); i++)
- {
- if(esArbol(aristas[i]))
- {
- add(aristas[i]);
- save(aristas[i]);
- }
- }
- cout << cable << endl;
- for(int i = 1; i < grafoF.size(); i++)
- {
- cout << i << " ";
- for(int j = 0; j < grafoF[i].size(); j++)
- {
- cout << grafoF[i][j] << " ";
- }
- cout << endl;
- }
- }
- bool esArbol(arista a)
- {
- int n1 = a.desde;
- int n2 = a.hacia;
- int c1 = idcomp[n1];
- int c2 = idcomp[n2];
- return (c1 != c2);
- }
- void add(arista a)
- {
- int n1 = a.desde, n2 = a.hacia;
- int c1 = idcomp[n1], c2 = idcomp[n2];
- int t1 = comp[c1].size();
- int t2 = comp[c2].size();
- if(t1 > t2)
- {
- swap(n1,n2);
- swap(c1,c2);
- swap(t1,t2);
- }
- for(int i = 0; i < t1; i++)
- {
- int n = comp[c1][i];
- idcomp[n] = c2;
- comp[c2].push_back(n);
- }
- }
- void save (arista a)
- {
- cable += a.c;
- grafoF[a.desde].push_back(a.hacia);
- grafoF[a.hacia].push_back(a.desde);
- }
- };
- int main()
- {
- grafo g;
- g.entrada();
- g.kruskal();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement