Solution UVA: 908 - Re-connecting Computer Sites

 

Problem:
https://onlinejudge.org/external/9/908.pdf

 

Suggest:

- Use kruskal algorithm

-> Number edge of kruskal in problem is old edge + new edge 

(high-speed lines = edge)

 

Code:

#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,s1=0,m1,m2;

int fa[N];

struct Arr{

int u,v,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);

}

void Scanf(){

s1= 0;

FOR(i, 1, n-1)

cin >> a[i].u >> a[i].v >> a[i].w;

FOR(i, 1, n-1)

s1 += a[i].w;

cin >> m1;

FOR(i, 1, m1)

cin >> a[i].u >> a[i].v >> a[i].w;

cin >> m2;

FOR(i, m1+1, m1+m2)

cin >> a[i].u >> a[i].v >> a[i].w;

m = m1 + m2;

}

void Reset(){

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

}

void Solve(){

cout<<s1<<"\n";

int 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<<ans<<"\n";

}

int main(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

int cnt=0;

while(cin >> n){

if (cnt++ != 0){

cout<<"\n";

}

Scanf();

Reset();

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

Solve();

}

}