В городе есть n человек, и у каждого человека есть несколько друзей в городе.(если a друг b, то b также друг a) Мы хотим распространить слух между этими людьми, но сказать, что слух каждому человеку стоит c_i, но после этого человек распространяет слух между всеми своимидрузья бесплатно.
Мы хотим найти минимальную цену, чтобы распространить слух всем жителям города.На входе мы получаем n: количество человек.m: количество отношений.затем n целых чисел c_i: стоимость передачи слухов человеку i, а затем в m строках мы получаем два целых числа u, v в каждой строке, которые указывают, что u,v - друзья.(обратите внимание, что число людей начинается с 1 до n, но в массивах мы имеем от 0 до n-1)
Также n,m<=10E5 и c_i<=10E9
Я думаю, что эта проблема эквивалентна сумме минимальных элементов во всех связанных компонентах неориентированного графа.
Я нашел решение для этого в Интернете с C ++, но я хотел написать его на Java и поэтому написалПрограмма ниже с использованием DFS.Проблема в том, что когда я отправляю ответ онлайн-судье на сайте, где я нашел вопрос, он просто проходит только 3 из 20 тестов.Я хочу знать, какая часть моего решения неверна?
(сайт не на английском языке и на самом деле представляет собой систему онлайн-судей университета, но если вы хотите, я могу сделать ссылку на сайт)
Итоговый код, который прекрасно работает:
import java.util.LinkedList;
import java.util.Scanner;
class Graph {
int numberOfVertices;
LinkedList<Integer>[] graph;
boolean[] visited;
long[] costs;
Graph(int numberOfVertices,long[] costs) {
this.numberOfVertices = numberOfVertices;
this.graph = new LinkedList[numberOfVertices];
for (int v = 0; v < numberOfVertices; v++) {
graph[v] = new LinkedList<Integer>();
}
this.costs=costs;
this.visited = new boolean[numberOfVertices];
}
void addEdge(int u, int v) {
graph[u].add(v);
graph[v].add(u);
}
long dfs(int node, long mini) {
// Stores the minimum
mini = Math.min(mini, costs[ node]);
// Marks node as visited
visited[ node] = true;
// Traversed in all the connected nodes
for (int i : graph[ node]) {
if (!visited[ i])
mini = dfs(i, mini);
}
return mini;
}
void minimumSumConnectedComponents() {
// Initially sum is 0
long sum = 0L;
// Traverse for all nodes
for (int i = 0; i < numberOfVertices; i++) {
if (!visited[i]) {
sum += dfs(i, costs[i]);
}
}
// Returns the answer
System.out.println(sum);
}
}
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int numberOfVertices,numberOfRelations;
numberOfVertices=input.nextInt();
numberOfRelations=input.nextInt();
long [] costs = new long[numberOfVertices];
for (int i =0;i<numberOfVertices;i++)
{
costs[i]=input.nextLong();
}
Graph g = new Graph(numberOfVertices,costs);
for (int i =0;i<numberOfRelations;i++)
{
int v1,v2;
v1=input.nextInt();
v2=input.nextInt();
g.addEdge(v1-1,v2-1);
}
g.minimumSumConnectedComponents();
}
}
Старый код, который имеет некоторые проблемы:
import java.util.Scanner;
import java.util.Vector;
class Graph {
Integer numberOfVertices;
Vector<Integer>[] graph;
boolean[] visited;
Long[] costs;
Graph(Integer numberOfVertices,Long[] costs) {
this.numberOfVertices = numberOfVertices;
this.graph = new Vector[numberOfVertices];
for (Integer v = 0; v < numberOfVertices; v++) {
graph[v] = new Vector<Integer>();
}
this.costs = new Long[numberOfVertices];
for (Integer v = 0; v < numberOfVertices; v++) {
this.costs[v] = costs[v];
}
this.visited = new boolean[numberOfVertices];
}
void addEdge(Integer u, Integer v) {
graph[u].add(v);
graph[v].add(u);
}
void dfs(Integer node, Long mini) {
// Stores the minimum
mini = Math.min(mini, costs[(Integer) node]);
// Marks node as visited
visited[(Integer) node] = true;
// Traversed in all the connected nodes
for (Integer i : graph[(Integer) node]) {
if (!visited[(Integer) i])
dfs(i, mini);
}
}
void minimumSumConnectedComponents() {
// Initially sum is 0
Long sum = 0L;
// Traverse for all nodes
for (Integer i = 0; i < numberOfVertices; i++) {
if (!visited[i]) {
Long mini = costs[i];
dfs(i, mini);
sum += mini;
}
}
// Returns the answer
System.out.println(sum);
}
}
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
Integer numberOfVertices,numberOfRelations;
numberOfVertices=input.nextInt();
numberOfRelations=input.nextInt();
Long [] costs = new Long[numberOfVertices];
for (Integer i =0;i<numberOfVertices;i++)
{
costs[i]=input.nextLong();
}
Graph g = new Graph(numberOfVertices,costs);
for (Integer i =0;i<numberOfRelations;i++)
{
Integer v1,v2;
v1=input.nextInt();
v2=input.nextInt();
g.addEdge(v1-1,v2-1);
}
g.minimumSumConnectedComponents();
}
}
Примеры тестовых случаев:
5 2
2 5 3 4 8
1 4
4 5
Expected Output: 10
10 0
1 2 3 4 5 6 7 8 9 10
Expected Output: 55
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
Expected Output: 15
Моя программа проходит этот пример тестовых случаев, но для многих неизвестных тестов она получает неправильный ответ.