无向图所有连通分量的最小元素之和

Question

In a city, there is n persons and each person has some friends in the city. (if a is friend of b then b is also friend of a) We want to spread a rumor between these persons but saying the rumor to each person has a cost c_i but after that, the person spread the rumor between all of its friends for free.

We want to find minimum cost to spread the rumor to all persons in the city. In the input we get n: number of persons. m: number of relations. then n integers c_i: cost of saying the rumor to person i and then in m lines, we get two integers u,v in each line which indicates u,v are friends. (note that number of person start from 1 to n but in arrays we have from 0 to n-1)

Also n,m<=10E5 and c_i<=10E9

我觉得这道题等价于无向图所有连通分量的最小元素求和

我在互联网上用 C++ 找到了一个解决方案，但我想用 Java 编写它，所以使用 dfs 编写了下面的程序。问题是，当我在发现问题的网站上将答案提交给在线评委时，它只通过了 20 项测试中的 3 项。我想知道我的解决方案的哪一部分是错误的？

（网站不是英文的，实际上是一个大学的在线评委系统，如果你想要的话，我可以link到网站）

完全可以正常工作的最终代码：

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

我的程序通过了这个示例测试用例，但是对于很多未知的测试用例它得到了错误的答案。

Answer 1

这些行不符合您的要求：

    // Stores the minimum
    mini = Math.min(mini, costs[(Integer) node]);

如果他们改变了调用者的 mini，那么您的代码在其他方面似乎是正确的（假设没有堆栈溢出）。我的建议是 return mini 的新值供调用者使用：

Long 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])
            mini = dfs(i, mini);
    }

    return mini;
}

void minimumSumConnectedComponents() {
    // Initially sum is 0
    Long sum = 0L;

    // Traverse for all nodes
    for (Integer i = 0; i < numberOfVertices; i++) {
        if (!visited[i]) {
            sum += dfs(i, costs[i]);
        }
    }

    // Returns the answer

    System.out.println(sum);
}

无向图所有连通分量的最小元素之和

Sum of the minimum elements in all connected components of an undirected graph

java

algorithm

graph

depth-first-search