Solution UVA: 10397 - Connect the Campus

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10397 - Connect the Campus	Accepted	C++11	0.060	0.000	703	30 secs ago

Suggest:
- The first, we calc distance of buildings (w) and create edge with 3 prameter u,v,w for kruskal

- Second, we create edge with w=0 for buildings had cable ago

- Finaly, use kruskal :))

#include<bits/stdc++.h>

#define N 1000111

#define FOR(i, a, b) for(int i=a; i<=b; i++)

using namespace std;

int n,m,u,v;

int fa[N];

int x[N], y[N];

struct Arr{

 int u,v;

 double w;

};

Arr a[N];

bool cmd(Arr a, Arr b){

 return a.w < b.w;

}

int root(int u){

 return fa[u]=( fa[u]==u ? u : root(fa[u]) );

}

void join(int u, int v){

 fa[root(u)]=root(v);

}

double dis(int a, int b, int c, int d){

    return sqrt(pow(c - a, 2) + pow(d - b, 2));

}

void Reset(){

 FOR(i, 1, n) fa[i]= i;

}

void Solve(){

 double ans=0;

 FOR(i, 1, m)

  if (root(a[i].u) != root(a[i].v)){

   

   join(a[i].u, a[i].v);

   ans+= a[i].w;

   if (--n == 1) break;

  }

 cout<<fixed<<setprecision(2)<<ans<<"\n";

}

void Scanf(){

   

     while(cin >> n){

     

         FOR(i, 1, n) cin >> x[i] >> y[i];

         

         m= 0;

         FOR(i, 1, n-1)

         FOR(j, i+1, n){

            a[++m].u = i;

            a[m].v = j;

            a[m].w = dis(x[i], y[i], x[j], y[j]);

           

         }

         

         int m0; cin >> m0;

         while(m0--){

           

            cin >> u >> v;

            a[++m].u = u;

            a[m].v = v;

            a[m].w = 0;

         }

   

         Reset();

         sort(a+1, a+1+m, cmd); // m

         Solve();  

     }

}

int main(){

 ios::sync_with_stdio(false);

 cin.tie(nullptr);

 

 Scanf();

}