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)
