Roads and Libraries


Problem Statement :


Determine the minimum cost to provide library access to all citizens of HackerLand. There are n cities numbered from 1 to n. Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in cities. A citizen has access to a library if:

1. Their city contains a library.
2. They can travel by road from their city to a city containing a library.


unction Description

Complete the function roadsAndLibraries in the editor below.
roadsAndLibraries has the following parameters:

int n: integer, the number of cities
int c_lib: integer, the cost to build a library
int c_road: integer, the cost to repair a road
int cities[m][2]: each cities[ i ] contains two integers that represent cities that can be connected by a new road
Returns
- int: the minimal cost

Input Format

The first line contains a single integer q, that denotes the number of queries.

The subsequent lines describe each query in the following format:
- The first line contains four space-separated integers that describe the respective values of n , m , c_lib and c_road, the number of cities, number of roads, cost of a library and cost of a road.
- Each of the next m lines contains two space-separated integers, u[ i ] and v[ i ] , that describe a bidirectional road that can be built to connect cities c[ i ] and v[ i ].


Sample Input

STDIN       Function
-----       --------
2           q = 2
3 3 2 1     n = 3, cities[] size m = 3, c_lib = 2, c_road = 1
1 2         cities = [[1, 2], [3, 1], [2, 3]]
3 1
2 3
6 6 2 5     n = 6, cities[] size m = 6, c_lib = 2, c_road = 5
1 3         cities = [[1, 3], [3, 4],...]
3 4
2 4
1 2
2 3
5 6


Sample Output


4
12



Solution :


                        #include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define swap_(x, y) { int z = x; x = y; y = z; }

typedef long long ll;

typedef struct L
{
  int *xs;
  int n;
  int size;
} L;

void add(L *l, int x)
{
  if (l->n == l->size)
  {
    l->size *= 2;
    l->xs = realloc(l->xs, sizeof(int) * l->size);
    assert(l->xs);
  }
  l->xs[l->n++] = x;
}

void ini(L *l)
{
  l->n = 0;
  l->size = 4;
  l->xs = malloc(sizeof(int) * l->size);
  assert(l->xs);
}

L *create()
{
  L *l = malloc(sizeof(L));
  assert(l);
  ini(l);
  return l;
}
  
L *ls[100000];

ll solve()
{
  int n, m;
  ll rc, lc;
  scanf("%d%d%lld%lld", &n, &m, &lc, &rc);
  for (int i = 0; i < n; ++i)
  {
    ls[i] = NULL;
  }
  int count = 0;
  for (int _i = 0; _i < m; ++_i)
  {
    int i, j;
    scanf("%d%d", &i, &j);
    i--; j--;
    if (lc <= rc)
    {
      continue;
    }
    if (ls[i] == ls[j])
    {
      if (ls[i] == NULL)
      {
        L *l = create();
        add(l, i);
        add(l, j);
        count++;
        ls[i] = l;
        ls[j] = l;
      }
    }
    else
    {
      count++;
      if (ls[i] == NULL)
      {
        swap_(i, j);
      }
      if (ls[j] == NULL)
      {
        add(ls[i], j);
        ls[j] = ls[i];
      }
      else
      {
        if (ls[i]->n < ls[j]->n)
        {
          swap_(i, j);
        }
        L *l = ls[j];
        for (int p = 0; p < l->n; ++p)
        {
          int k = l->xs[p];
          add(ls[i], k);
          ls[k] = ls[i];
        }
        free(l->xs);
        free(l);
      }
    }
  }
  return rc * count + lc * (n - count);
}

int main()
{
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i)
  {
    ll min_cost = solve();
    printf("%lld\n", min_cost);
  }
  return 0;
}
                    

                        In   C++ :





#include <bits/stdc++.h>
using namespace std;
vector<int> p;
int f(int a){return p[a]==a?a:p[a]=f(p[a]);}
void u(int a, int b){p[f(a)] = f(b);}
signed main()
{
    int T;cin >> T;while(T--){
        int N, M, a, b;
        long long c, d;
        cin >> N >> M >> c >> d;
        p.clear();p.resize(N);
        iota(p.begin(), p.end(), 0);
        while(M--){
            cin >> a >> b;
            --a, --b;
            u(a, b);
        }
        int comp=0;
        for(int i=0;i<N;++i){
            if(p[i]==i)++comp;
        }
        cout << (comp*c+(N-comp)*min(c, d)) << "\n";
    }

    return 0;
}
                    

                        In   C++ :





#include <bits/stdc++.h>
using namespace std;
vector<int> p;
int f(int a){return p[a]==a?a:p[a]=f(p[a]);}
void u(int a, int b){p[f(a)] = f(b);}
signed main()
{
    int T;cin >> T;while(T--){
        int N, M, a, b;
        long long c, d;
        cin >> N >> M >> c >> d;
        p.clear();p.resize(N);
        iota(p.begin(), p.end(), 0);
        while(M--){
            cin >> a >> b;
            --a, --b;
            u(a, b);
        }
        int comp=0;
        for(int i=0;i<N;++i){
            if(p[i]==i)++comp;
        }
        cout << (comp*c+(N-comp)*min(c, d)) << "\n";
    }

    return 0;
}
                    

                        In   Python3 :





#!/bin/python3

import sys

def find_root(roots, city):
    i = roots[city]
    while(i != roots[i]):
        i = roots[i]
    return roots[i]

q = int(input().strip())
for a0 in range(q):
    n,m,x,y = input().strip().split(' ')
    n,m,x,y = [int(n),int(m),int(x),int(y)]
    
    root = [x for x in range(n+1)]
    cost = 0
    
    if(x <= y):
        print(n*x)
        for _ in range(m):
            x = input()
        continue
    for a1 in range(m):
        city_1,city_2 = input().strip().split(' ')
        city_1,city_2 = [int(city_1),int(city_2)]
        temp1 = find_root(root, city_1)
        temp2 = find_root(root, city_2)
        if(temp1 != temp2):
            root[temp1] = temp2
            cost += y
    for i in range(1,n+1):
        if(i == root[i]):
            cost +=x
    print(cost)
                    



Copyrights © ClownMonster's Inc