Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std ;
- #define M 500000
- #define pii pair<int , int >
- #define mp make_pair
- #define pf printf
- #define sf scanf
- #define sf1(a ) scanf("%d",&a)
- #define pb push_back
- #define sf2(a, b) scanf("%d%d",&a ,&b)
- #define rep(i,n) for(i = 0 ; i< n ;i++ )
- int par[M] , num ;
- struct vertex {
- int u , v , w ;
- };
- vector <vertex >node;
- bool comp(vertex p , vertex q ){
- return p.w < q.w ;
- }
- int find(int a ){
- if(par[a ] == a ) return a ;
- else return par[a ] = find(par[a ]);
- }
- void make(int a , int b ){
- int u = find(u );
- int v = find(v );
- if(u != v ) par[u] = v ;
- }
- int mst(){
- int i , j ,k ;
- rep(i , num ) par[i] = i ;
- sort(node.begin() , node.end() , comp);
- int cost = 0;
- for(i = 0 ; i < node.size() ; i++){
- if(find(node[i].u ) != find(node[i].v ) )
- {
- make(node[i].u , node[i].v );
- cost += node[i].w ;
- }
- }
- return cost;
- }
- map<pair<int ,int > , int > m;
- int main(){
- int i , j ,k , print = 0;
- while(scanf("%d",&num ) == 1){
- if(print != 0) pf("\n");
- print = 1 ;
- k = num -1 ;
- int cost = 0;
- while(k--){
- vertex var ;
- scanf("%d%d%d",&var.u, &var.v , &var.w );
- node.pb(var);
- cost += var.w ;
- m[mp(var.u , var.v)] = 1 ;
- }
- int prev ;
- prev = mst();
- sf1(k );
- num += k ;
- int hold = k;
- while(k--){
- vertex var ;
- scanf("%d%d%d",&var.u, &var.v , &var.w );
- node.pb(var);
- m[mp(var.u , var.v)] = 1 ;
- }
- num -= hold;
- int nw ;
- nw = mst();
- sf1(k );
- while(k--){
- vertex var ;
- pii it ;
- scanf("%d%d%d",&var.u, &var.v , &var.w );
- it = mp(var.u , var.v);
- if(m.find(it) == m.end()){
- num++;
- node.pb(var);
- m[it ] = 1 ;
- }
- }
- // int brand ;
- // brand = mst();
- pf("%d %d\n",prev , nw );
- }
- return 0 ;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement