Advertisement
Guest User

Untitled

a guest
Apr 18th, 2015
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int cnt=0;
  6.  
  7. struct co
  8. {
  9.     double x,y;
  10.     int id;
  11.     co(double a,double b)
  12.     {
  13.         id=cnt++;
  14.         x=a;
  15.         y=b;
  16.     }
  17. };
  18.  
  19. struct edge
  20. {
  21.     int u,v;
  22.     double w;
  23.     edge(int a,int b,double c):u(a),v(b),w(c){}
  24.     bool operator<(const edge& p) const
  25.     {
  26.         return w<p.w;
  27.     }
  28. };
  29.  
  30. vector<edge> ed;
  31. vector<co> nd;
  32. vector<int> par;
  33.  
  34. int find_par(int n)
  35. {
  36.     return (n==par[n]) ? n : find_par(par[n]);
  37. }
  38.  
  39. double mst(int n)
  40. {
  41.     par.clear();
  42.     par.resize(n);
  43.     for(int i=0;i<n;i++) par[i]=i;
  44.  
  45.     double w=0; int c=0;
  46.  
  47.     sort(ed.begin(),ed.end());
  48.  
  49.     int l=ed.size();
  50.  
  51.     for(int i=0;i<l;i++)
  52.     {
  53.         int a=find_par(ed[i].u);
  54.         int b=find_par(ed[i].v);
  55.         if(a!=b)
  56.         {
  57.             par[b]=a;
  58.             w+=ed[i].w;
  59.             c++;
  60.             if(c==n-1) break;
  61.         }
  62.     }
  63.     return w;
  64. }
  65.  
  66. int main()
  67. {
  68.     int tc;
  69.     freopen("in.txt","r",stdin);
  70.     while(cin>>tc)
  71.     {
  72.         //scanf("\n");
  73.         while(tc--)
  74.         {
  75.             nd.clear();
  76.             ed.clear();
  77.             int n;
  78.             cin>>n;
  79.             while(n--)
  80.             {
  81.                 double a,b;
  82.                 cin>>a>>b;
  83.                 nd.push_back(co(a,b));
  84.             }
  85.             //scanf("\n");
  86.             n=nd.size();
  87.             for(int i=0;i<n-1;i++)
  88.             {
  89.                 int x1=nd[i].x;
  90.                 int y1=nd[i].y;
  91.                 for(int j=i+1;j<n;j++)
  92.                 {
  93.                     int x2=nd[j].x;
  94.                     int y2=nd[j].y;
  95.                     double d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  96.                     ed.push_back(edge(nd[i].id,nd[j].id,d));
  97.                 }
  98.             }
  99.             printf("%.2lf\n",mst(n));
  100.             if(tc) cout<<endl;
  101.         }
  102.     }
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement