Cerinta completa

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

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

Example

The following figure is a sample map of HackerLand where the dotted lines denote possible roads:

image



The cost of building any road is , and the cost to build a library in any city is . Build roads at a cost of and libraries for a cost of . One of the available roads in the cycle is not necessary.

There are queries, where each query consists of a map of HackerLand and value of and . For each query, find the minimum cost to make libraries accessible to all the citizens.

Function 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 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 , 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 , , and , the number of cities, number of roads, cost of a library and cost of a road.
– Each of the next lines contains two space-separated integers, and , that describe a bidirectional road that can be built to connect cities and .

Constraints

  • Each road connects two distinct cities.

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

Explanation

Perform the following queries:

  1. HackerLand contains cities and can be connected by bidirectional roads. The price of building a library is and the price for repairing a road is .
    image

    The cheapest way to make libraries accessible to all is to:

    • Build a library in city at a cost of .
    • Build the road between cities and at a cost of .
    • Build the road between cities and at a cost of .

    This gives a total cost of . Note that the road between cities and does not need to be built because each is connected to city .

  2. In this scenario it is optimal to build a library in each city because the cost to build a library is less than the cost to build a road.
    image

    There are cities, so the total cost is .

Limbajul de programare folosit: java8

Cod:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int q = sc.nextInt();
		for (int tc = 0; tc < q; tc++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int libCost = sc.nextInt();
			int roadCost = sc.nextInt();

			@SuppressWarnings("unchecked")
			List<Integer>[] adjacentLists = new List[n + 1];
			for (int i = 1; i < adjacentLists.length; i++) {
				adjacentLists[i] = new ArrayList<>();
			}

			for (int i = 0; i < m; i++) {
				int city1 = sc.nextInt();
				int city2 = sc.nextInt();

				adjacentLists[city1].add(city2);
				adjacentLists[city2].add(city1);
			}

			System.out.println(solve(adjacentLists, libCost, roadCost));
		}

		sc.close();
	}

	static long solve(List<Integer>[] adjacentLists, int libCost, int roadCost) {
		long minCost = Long.MAX_VALUE;
		for (int libNum = computeComponentNum(adjacentLists), roadNum = adjacentLists.length - 1
				- libNum; roadNum >= 0; libNum++, roadNum--) {
			minCost = Math.min(minCost, (long) libNum * libCost + (long) roadNum * roadCost);
		}
		return minCost;
	}

	static int computeComponentNum(List<Integer>[] adjacentLists) {
		boolean[] visited = new boolean[adjacentLists.length];
		int componentNum = 0;
		for (int i = 1; i < visited.length; i++) {
			if (!visited[i]) {
				search(adjacentLists, visited, i);
				componentNum++;
			}
		}
		return componentNum;
	}

	static void search(List<Integer>[] adjacentLists, boolean[] visited, int city) {
		if (visited[city]) {
			return;
		}

		visited[city] = true;
		for (int adjacent : adjacentLists[city]) {
			search(adjacentLists, visited, adjacent);
		}
	}
}

Scor obtinut: 1.0

Submission ID: 464602901

Link challenge: https://www.hackerrank.com/challenges/torque-and-development/problem

Roads and Libraries