在一座城市里，有n个人，每个人在这个城市里都有一些朋友。如果a是b的朋友，那么b也是a的朋友。我们想要在这些人之间散布一个谣言，但告诉每个人这个谣言是有成本ci的，但之后，这个人会免费将这个谣言传播给他所有的朋友。
我们想要找到将谣言传播给全城所有人的最小成本。在输入中，我们得到了n：人数。m：关系数量。然后n个整数ci：向人i传递谣言的成本；在m行中，我们得到两个整数u，v，表示u和v是朋友（注意，人数从1到n，但在数组中我们从0到n-1）。
此外，n、m<=10E5，ci<=10E9。
我认为这个问题等价于无向图所有连通分量中最小元素的总和。
我在网上找到了一个C++的解决方案，但我想用Java编写它，所以使用dfs编写了下面的程序。问题是当我将答案提交到我找到问题的网站的在线评测系统时，它只能通过20个测试中的3个。我想知道我的解决方案的哪个部分出了问题？
(该网站不是英语网站，实际上是大学的在线评测系统，但如果您需要，我可以提供链接）
完整可用的最终代码如下：
我们想要找到将谣言传播给全城所有人的最小成本。在输入中，我们得到了n：人数。m：关系数量。然后n个整数ci：向人i传递谣言的成本；在m行中，我们得到两个整数u，v，表示u和v是朋友（注意，人数从1到n，但在数组中我们从0到n-1）。
此外，n、m<=10E5，ci<=10E9。
我认为这个问题等价于无向图所有连通分量中最小元素的总和。
我在网上找到了一个C++的解决方案，但我想用Java编写它，所以使用dfs编写了下面的程序。问题是当我将答案提交到我找到问题的网站的在线评测系统时，它只能通过20个测试中的3个。我想知道我的解决方案的哪个部分出了问题？
(该网站不是英语网站，实际上是大学的在线评测系统，但如果您需要，我可以提供链接）
完整可用的最终代码如下：
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
我的程序可以通过这些例子测试，但是对于许多未知的测试案例，它的答案是错误的。