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 :
Solution in C :
In C :
#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;
}
Solution in C++ :
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;
}
Solution in Java :
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int q = in.nextInt();
for(int a0 = 0; a0 < q; a0++){
int n = in.nextInt();
int m = in.nextInt();
int x = in.nextInt();
int y = in.nextInt();
List<List<Integer>> groups = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++){
List<Integer> group = new ArrayList<Integer>();
group.add(i);
groups.add(group);
}
boolean[] enabled = new boolean[n];
for (int i = 0; i < n; i++)
enabled[i] = true;
int[] pointers = new int[n];
for (int i = 0; i < n; i++)
pointers[i] = i;
for(int a1 = 0; a1 < m; a1++){
int city_1 = in.nextInt() - 1;
int city_2 = in.nextInt() - 1;
int p1 = pointers[city_1];
int p2 = pointers[city_2];
if (p1 != p2){
for (int i : groups.get(p2)){
pointers[i] = p1;
groups.get(p1).add(i);
}
enabled[p2] = false;
}
}
long total = 0;
for (int i = 0; i < n; i++){
if (enabled[i]){
int size = groups.get(i).size();
total += Math.min(size * x, x + (size - 1) * y);
}
}
System.out.println(total);
}
}
}
Solution in Python :
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)
View More Similar Problems
Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →