Created
May 10, 2017 20:05
-
-
Save V0L0DYMYR/a92e402b4578a166fa987be82c5e1963 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import graph.Edge; | |
| import java.util.*; | |
| import java.util.PriorityQueue; | |
| public class PrimSolution { | |
| private List<Set<Edge>> graph = new ArrayList<>(); | |
| public static void main(String[] args) { | |
| Scanner in = new Scanner(System.in); | |
| int n = in.nextInt(); | |
| int m = in.nextInt(); | |
| List<Edge> edges = new ArrayList<>(); | |
| for (int i = 0; i < m; i++) { | |
| edges.add(Edge.edge(in.nextInt(), in.nextInt(), in.nextInt())); | |
| } | |
| PrimSolution ps = new PrimSolution(); | |
| ps.addAllEdges(edges); | |
| PriorityQueue<Edge> pq = new PriorityQueue<>(); | |
| pq.addAll(ps.getEdges(0)); | |
| Set<Integer> visitedVertexes = new HashSet<>(); | |
| visitedVertexes.add(0); | |
| Set<Edge> mst = new HashSet<>(); | |
| Set<Edge> cut = new HashSet<>(); | |
| cut.addAll(ps.getEdges(0)); | |
| while (!pq.isEmpty()) { | |
| Edge edge = pq.poll(); | |
| if (!(visitedVertexes.contains(edge.W()) && visitedVertexes.contains(edge.V()))) { | |
| mst.add(edge); | |
| visitedVertexes.add(edge.W()); | |
| visitedVertexes.add(edge.V()); | |
| pq.addAll(ps.getEdges(edge.W())); | |
| pq.addAll(ps.getEdges(edge.V())); | |
| } | |
| } | |
| int weight = 0; | |
| for(Edge edge: mst){ | |
| weight+=edge.weight(); | |
| } | |
| System.out.println(weight); | |
| } | |
| public void addAllEdges(Collection<Edge> edges) { | |
| int n = -1; | |
| for (Edge edge : edges) { | |
| n = Math.max(Math.max(edge.V(), edge.W()), n); | |
| } | |
| for (int i = 0; i < n +1; i++) { | |
| graph.add(new HashSet<>()); | |
| } | |
| for (Edge edge : edges) { | |
| graph.get(edge.V()).add(edge); | |
| graph.get(edge.W()).add(edge); | |
| } | |
| } | |
| public Set<Edge> getEdges(int v) { | |
| return graph.get(v); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment