java - 无向图的所有连通分量中最小元素的总和

问题描述

在一个城市里，n有人，每个人在城市里都有一些朋友。（如果a是b的朋友那么b也是a的朋友）我们想在这些人之间散布谣言，但是向每个人说谣言是有代价的c_i，但是之后，这个人在所有朋友之间免费散布谣言.

我们想找到将谣言传播给全市所有人的最低成本。在输入中我们得到n：人数。m: 关系数。然后n整数c_i：向人说谣言的成本，i然后在行中m，我们得到两个整数u，v在每行中表示u,v是朋友。（请注意，人数从1to开始，n但在数组中我们有 from 0to n-1）

还有n,m<=10E5和c_i<=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

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

标签： javaalgorithmgraphdepth-first-search

java - 无向图的所有连通分量中最小元素的总和

问题描述

解决方案

推荐阅读