Сумма минимальных элементов во всех связных компонентах неориентированного графа - PullRequest
0 голосов
/ 01 марта 2019

В городе есть 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

Моя программа проходит этот пример тестовых случаев, но для многих неизвестных тестов она получает неправильный ответ.

1 Ответ

0 голосов
/ 01 марта 2019

Эти строки не делают того, что вы хотите:

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

Если они мутировали mini вызывающей стороны, то ваш код кажется правильным (при условии отсутствия переполнения стека).Я предлагаю вернуть новое значение 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);
}
...