See if can give a solution

Правка en1, от najmul.csebuet, 2020-11-11 16:00:44

I am trying to solve following problem.

https://open.kattis.com/problems/uprooted

Any hint and more better a solution is appreciated. I am trying a lot but not solved yet.


import java.io.*; import java.nio.file.Files; import java.nio.file.Paths; import java.util.*; public class A2_Uprooted { public static Scanner sc; public static PrintWriter out; public static void main(String[] args) throws IOException { boolean fileInOut = !A2_Uprooted.class.getPackage().getName().isEmpty(); sc = new Scanner(new BufferedReader(new InputStreamReader(fileInOut ? A2_Uprooted.class.getResourceAsStream("in.txt") : System.in))); out = new PrintWriter(new BufferedOutputStream(fileInOut ? new FileOutputStream("out.txt") : System.out), true); int totalTC = fileInOut ? sc.nextInt() : sc.nextInt(); for (int t = 1; t <= totalTC; t++) { int N = sc.nextInt(); int M = sc.nextInt(); int S = sc.nextInt(); Map<Integer, List<Edge>> adjList = new HashMap<>(); for (int index = 1; index <= M; index++) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); Edge e = new Edge(a, b, c, index); List<Edge> listA = adjList.getOrDefault(a, new ArrayList<>()); listA.add(e); adjList.put(a, listA); List<Edge> listB = adjList.getOrDefault(b, new ArrayList<>()); listB.add(e); adjList.put(b, listB); } int[][] sequences = new int[S][N - 1]; for (int i = 0; i < S; i++) { for (int j = 0; j < N - 1; j++) { sequences[i][j] = sc.nextInt(); } } new A2_Uprooted().solution(N, M, S, adjList, sequences); } if (fileInOut) { String[] ansFileText = Files.readAllLines(Paths.get(A2_Uprooted.class.getResource("ans.txt").getFile())).toArray(new String[0]); String[] outFileText = Files.readAllLines(Paths.get("out.txt")).toArray(new String[0]); if (Arrays.equals(ansFileText, outFileText)) System.out.println("ALL TEST CASES PASSED!"); else for (int i = 0; i < ansFileText.length; i++) if (!ansFileText[i].equals(outFileText[i])) System.out.println("Test Case #" + (i + 1) + ": Failed"); } } private boolean isImpossible(int n, int m, int s, Map<Integer, List<Edge>> adjList, int[][] sequences) { for (int row = 0; row < s; row++) { Map<Integer, Boolean> nodeMap = new HashMap<>(); nodeMap.put(1, true); for (int column = 0; column < n - 1; column++) { int node = sequences[row][column]; if (nodeMap.getOrDefault(node, false)) continue; List<Edge> edgeList = adjList.getOrDefault(node, new ArrayList<>()); Edge maxEdge = null; for (Edge edge : edgeList) { int neighbour = edge.getNeighbour(node); if (nodeMap.getOrDefault(neighbour, false)) { if (maxEdge == null || maxEdge.c < edge.c) { maxEdge = edge; } } } if (maxEdge != null) { nodeMap.put(node, true); //edgeSet.add(maxEdge); } else { out.println("IMPOSSIBLE"); return true; } } } return false; } public void solution(int n, int m, int s, Map<Integer, List<Edge>> adjList, int[][] sequences) { if (isImpossible(n, m, s, adjList, sequences)) { return; } //Now it has a solution must Set<Edge> edgeSetGlobal = new HashSet<>(); for (int row = 0; row < s; row++) { Map<Integer, Boolean> nodeMap = new HashMap<>(); nodeMap.put(1, true); Map<Integer, List<Edge>> nodeListMap = new HashMap<>(); for (int column = 0; column < n - 1; column++) { int node = sequences[row][column]; if (nodeMap.getOrDefault(node, false)) continue; List<Edge> edgeList = adjList.getOrDefault(node, new ArrayList<>()); List<Edge> tempList = new ArrayList<>(); for (Edge edge : edgeList) { int neighbour = edge.getNeighbour(node); if (nodeMap.getOrDefault(neighbour, false)) { nodeMap.put(node, true); tempList.add(edge); } } if (tempList.isEmpty()) { out.println("IMPOSSIBLE"); return; } List<Edge> nodeList = nodeListMap.getOrDefault(node, new ArrayList<>()); } var intersection = edgeSetGlobal.retainAll(edgeSet); //edgeSetGlobal.addAll(edgeSet); System.out.println(); } System.out.println(); Edge[] arr = new Edge[edgeSetGlobal.size()]; edgeSetGlobal.toArray(arr); out.println(arr.length); for(int i = 0; i < arr.length - 1; ++i) { //out.print(edgeSet.get(i).index + " "); out.println(arr[i].desc()); } out.println(arr[arr.length - 1].desc()); } } class Edge { int a, b, c, index; Edge(int a, int b, int c, int index) { this.a = a; this.b = b; this.c = c; this.index = index; } int getNeighbour(int one) { if (a == one) return b; return a; } String desc() { return "(" + a + "," + b + "), weight: " + c + ", " + "Index = " + index; } }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский najmul.csebuet 2020-11-11 21:49:43 7935
en5 Английский najmul.csebuet 2020-11-11 16:22:57 51
en4 Английский najmul.csebuet 2020-11-11 16:19:33 81
en3 Английский najmul.csebuet 2020-11-11 16:05:23 0 (published)
en2 Английский najmul.csebuet 2020-11-11 16:04:11 4 (saved to drafts)
en1 Английский najmul.csebuet 2020-11-11 16:00:44 6154 Initial revision (published)